Functional programming design pattern: Nested Iterators == Flattening

Here's a functional programming design pattern I uncovered. This may not be news to you, but it was a surprise to me. It cropped up when looking at something that needs parallelization to reduced the elapsed run time.

Consider this data collection process.

for h in some_high_level_collection(arg1):
    for l in h.some_low_level_collection(arg2):
        if some_filter(l):
            logger.info("Processing %s %s", h, l)
            some_function(h, l)

This is pretty common in devops world. You might be looking at all repositories in all github organizations. You might be looking at all keys in all AWS S3 buckets under a specific account. You might be looking at all tables owned by all schemas in a database.

It's helpful -- for the moment -- to stay away from taller tree structures like the file system. Traversing the file system involves recursion, and the pattern is slightly different there. We'll get to it, but what made this clear to me was a "simpler" walk through a two-layer hierarchy. 

The nested for-statements aren't really ideal. We can't apply any itertools techniques here. We can't trivially change this to a multiprocessing.map(). 

In fact, the more we look at this, the worse it is.

Here's something that's a little easier to work with:

def h_l_iter(arg1, arg2):
    for h in some_high_level_collection(arg1):
        for l in h.some_low_level_collection(arg2):
            if some_filter(l):
                logger.info("Processing %s %s", h, l)
                yield h, l

itertools.starmap(some_function, h_l_iter(arg1, arg2))

The data gathering has expanded to a few more lines of code. It gained a lot of flexibility. Once we have something that can be used with starmap, it can also be used with other itertools functions to do additional processing steps without breaking the loops into horrible pieces.

I think the pattern here is a kind of "Flattened Map" transformation. The initial design, with nested loops wrapping a process wasn't a good plan. A better plan is to think of the nested loops as a way to flatten the two tiers of the hierarchy into a single iterator. Then a mapping can be applied to process each item from that flat iterator.

Extracting the Filter

We can now tease apart the nested loops to expose the filter. In the version above, the body of the h_l_iter() function binds log-writing with the yield. If we take those two apart, we gain the flexibility of being able to change the filter (or the logging) without an awfully complex rewrite.

T = TypeVar('T')
def logging_iter(source: Iterable[T]) -> Iterator[T]:
    for item in source:
        logger.info("Processing %s", item)
        yield item

def h_l_iter(arg1, arg2):
    for h in some_high_level_collection(arg1):
        for l in h.some_low_level_collection(arg2):
            yield h, l

raw_data = h_l_iter(arg1, arg2)
filtered_subset = logging_iter(filter(some_filter, raw_data))
itertools.starmap(some_function, filtered_subset)

Yes, this is still longer, but all of the details are now exposed in a way that lets me change filters without further breakage.

Now, I can introduce various forms of multiprocessing to improve concurrency.

This transformed a hard-wired set of nest loops, if, and function evaluation into a "Flattener" that can be combined with off-the shelf filtering and mapping functions.

I've snuck in a kind of "tee" operation that writes an iterable sequence to a log. This can be injected at any point in the processing.

Logging the entire "item" value isn't really a great idea. Another mapping is required to create sensible log messages from each item. I've left that out to keep this exposition more focused.

I'm sure others have seen this pattern, but it was eye-opening to me.

Full Flattening

The h_l_iter() function is actually a generator expression. A function isn't needed.

h_l_iter = (
    (h, l) 
    for h in some_high_level_collection(arg1) 
        for l in h.some_low_level_collection(arg2)
)

This simplification doesn't add much value, but it seems to be general truth. In Python, it's a small change in syntax and therefore, an easy optimization to make.

What About The File System?

When we're working with some a more deeply-nested structure, like the File System, we'll make a small change. We'll replace the h_l_iter() function with a recursive_walk() function.

def recursive_walk(path: Path) -> Iterator[Path]:
    for item in path.glob():
        if item.is_file():
            yield item
        elif item.is_dir():
            yield from recursive_walk(item)

This function has, effectively the same signature as h_l_iter(). It walks a complex structure yielding a flat sequence of items. The other functions used for filtering, logging, and processing don't change, allowing us to build new features from various combinations of these functions.

tl;dr

The too-long version of this is:

Replace for item in iter: process(item) with map(process, iter).

This pattern works for simple, flat items, nested structures, and even recursively-defined trees. It introduces flexibility with no real cost.

The other pattern in play is:

Any for item in iter: for sub-item in item:  processing is "flattening" a hierarchy into a sequence. Replace it with (sub-item for item in iter for sub-item in item).

These felt like blinding revelations to me.

Python exceptions considered an anti-pattern

https://sobolevn.me/2019/02/python-exceptions-considered-an-antipattern

While eloquent and thorough, I remain unconvinced that this is a significant improvement over try/except.

It's common enough in some functional languages to have strong support and a long, successful history.

I think it replaces one problem with another. It's not a "solution". It's an alternative. Instead of exceptions being raised, they're returned. Cool.

Why I like Functional Composition

After spending years developing a level of mastery over Object Oriented Design Patterns, I'm having a lot of fun understanding Functional Design Patterns.

The OO Design Patterns are helpful because they're concrete expressions of the S. O. L. I. D. design principles. Much of the "Gang of Four" book demonstrates the Interface Segregation, Dependency Injection, and Liskov Substitution Principles nicely. They point the way for implementing the Open/Closed and the Single Responsibility Principles.

For Functional Programming, there are some equivalent ideas, with distinct implementation techniques. The basic I, D, L, and S principles apply, but have a different look in a functional programming context. The Open/Closed principle takes on a radically different look, because it turns into an exercise in Functional Composition.

I'm building an Arduino device that collects GPS data. (The context for this device is the subject of many posts coming in the future.)

GPS devices generally follow the NMEA 0183 protocol, and transmit their data as sentences with various kinds of formats. In particular, the GPRMC and GPVTG sentences contain speed over ground   (SOG) data.

I've been collecting data in my apartment. And it's odd-looking. I've also collected data on my boat, and it doesn't seem to look quite so odd. Here's the analysis I used to make a more concrete conclusion.

def sog_study(source_path = Path("gps_data_gsa.csv")):
    with source_path.open() as source_file:
        rdr = csv.DictReader(source_file)
        sog_seq = list(map(float, filter(None, (row['SOG'] for row in rdr))))
        print("max {}\tMean {}\tStdev {}".format(
            max(sog_seq), statistics.mean(sog_seq), statistics.stdev(sog_seq)))

This is a small example of functional composition to build a sequence of SOG reports for analysis.

This code opens a CSV file with data extracted from the Arduino. There was some reformatting and normalizing done in a separate process: this resulted in a file in a format suitable for the processing shown above.

The compositional part of this is the list(map(float, filter(None, generator))) processing.

The (row['SOG'] for row in rdr) generator can iterate over all values from the SOG column. The filter(None, generator) will drop all None objects from the results, assuring that irrelevant sentences are ignored.

Given an iterable that can produce SOG values, the map(float, iterable) will convert the input strings into useful numbers. The surrounding list() creates a concrete list object to support summary statistics computations.

I'm really delighted with this kind of short, focused functional programming.

"But wait," you say. "How is that anything like the SOLID OO design?"

Remember to drop the OO notions. This is functional composition, not object composition.

ISP: The built-in functions all have well-segregated interfaces. Each one does a small, isolated job.

LSP: The concept of an iterable supports the Liskov Substitution Principle: it's easy to insert additional or different processing as long as we define functions that accept iterables as an argument and yield their values or return an iterable result.

For example.

def sog_gen(csv_reader):
    for row in csv_reader:
        yield row['SOG']

We've expanded the generator expression, (row['SOG'] for row in rdr), into a function. We can now use sog_gen(rdr) instead of the generator expression. The interfaces are the same, and the two expressions enjoy Liskov Substitution.

To be really precise, annotation with type hints can clarify this.  Something like sog_gen(rdr: Iterable[Dict[str, str]]) -> Iterable[str] would clarify this.

DIP: If we want to break this down into separate assignment statements, we can see how a different function can easily be injected into the processing pipeline. We could define a higher-order function that accepted functions like sog_gen, float, statistics.mean, etc., and then created the composite expression.

OCP: Each of the component functions is closed to modification but open to extension. We might want to do something like this: map_float = lambda source: map(float, source). The map_float() function extends map() to include a float operation. We might even want to write something like this.  map_float = lambda xform, source: map(xform, map(float, source)). This would look more like map(), with a float operation provided automatically.

SRP: Each of the built-in functions does one thing. The overall composition builds a complex operation from simple pieces.

The composite operation has two features which are likely to change: the column name and the transformation function. Perhaps we might rename the column from 'SOG' to 'sog'; perhaps we might use decimal() instead of float(). There are a number of less-likely changes. There might be a more complex filter rule, or perhaps a more complex transformation before computing the statistical summary.  These changes would lead to a different composition of the similar underlying pieces.

OOP and FP -- Objects vs. Functional -- Avoiding reductionist thinking

Real Quote (lightly edited to remove tangential nonsense.)

Recently, I watched a video and it stated that OO is about nouns and Functional programming is about the verbs. Also, ... Aspect-Oriented Programming with the e Verification Language  by David Robinson 

It would be nice to have a blog post which summarized the various mindset associated w/ the various paradigms.

Sigh.

I find the word "mindset" to be challenging.

Yes. All Turing Complete programming languages do have a kind of fundamental equivalence at the level of computing stuff represented as numbers. This, however, seems reductionist.

["All languages were one language to him. All languages were 'woddly'." Paraphrased from James Thurber's "The Great Quillow", a must-read.]

So. Beyond the core Turing Completeness features of a language, the rest is reduced to a difference in "mindset"? The only difference is how we pronounce "Woddly?"

"Mindset" feels reductionist. It replaces a useful summary of language features with a dismissive "mindset" categorization of languages. In a way, this seems to result from bracketing technology choices as "religious wars," where the passion for a particular choice outweighs the actual relevance; i.e., "All languages have problems, so use Java."

In my day job, I work with three kinds of Python problems:

• Data Science
• API Services
• DevOps/TechOps Automation

In many cases, one person can have all three problems. These aren't groups of people. These are problem domains.

I think the first step is to replace "mindset" with "problem domain". It's a start, but I'm not sure it's that simple.

When someone has a data science problem, they often solve it with purely function features of Python. Generally they do this via numpy, but I've been providing examples of generator expressions and comprehensions in my Code Dojo webinars. Generator expressions are an elegant, functional approach to working with stateless data objects.

In Python 3, the following kind of code doesn't create gigantic intermediate data structures. The functional transformations are applied to each item generated by the "source".

x = map(transform, source)
y = filter(selector_rule, x)
z = Counter(y)

I prefer to suggest that a fair amount of data analysis involves little or no mutation of state. Functional features of a language seem to work well with immutable data.

There is state change, but it's at a macro level. For example, the persistence of capturing data is a large-scale state change that's often implemented at the OS level, not the language level.

When someone's building an API, on the other hand, they're often working with objects that have a mutating state. Some elements of an API will involve state change, and objects model state change elegantly. RESTful API's can deserialize objects from storage, make changes, and serialize the modified object again.

[This summary of RESTful services is also reductionist, and therefore, possibly unhelpful.]

When there's mutability, then objects might be more appropriate than functions.

I'm reluctant to call this "mindset." It may not be "problem domain." It seems to be a model that involves mutable or immutable state.

When someone's automating their processing, they're wrestling with OS features, and OS management of state change. They might be installing stuff, or building Docker images, or gluing together items in a CI/CD pipeline, setting the SSL keys, or figuring out how to capture Behave output as part of Gherkin acceptance testing. Lots of interesting stuff that isn't the essential problem at hand, but is part of building a useful, automated solution to the problem.

The state in these problems is maintained by the OS. Application code may -- or may not -- try to model that state.

When doing Blue/Green deployments, for example, the blueness and greenness isn't part of the server farm, it's part of an internal model of how the servers are being used. This seems to be stateful; object-oriented programming might be helpful. When the information can be gleaned from asset management tools, then perhaps a functional processing stream is more important for gathering, deciding, and taking action.

I'm leaning toward the second view-point, and suggesting that some of the OO DevOps programming might be better looked at as functional map-filter-reduce processing. Something like

action_to_take = some_decision_pipeline(current state, new_deployment)

This reflects the questions of state change. It may not be the right abstraction though, because carrying out the action is, itself, a difficult problem that involves determining the state of the server farm, and then applying some change to one or more servers.

We often think of server state change as imperative in nature. It feels like object-oriented programming. There are steps, the object models those steps. I'm not sure that's right. I think there's a repeated "determine next action" cycle here. Sometimes it involves waiting for an action to finish. Yes, it sounds like polling the server farm. I'm not sure that's wrong. How else do you know a server is crashed except by polling it?

I think we've moved a long way from "mindset."

I think it's about fitting language features to a problem in a way that creates the right abstraction to capture (and eventually) solve the problem.

I haven't mentioned Aspect-Oriented Programming because it seems to cut across the functional/object state management boundary. It's a distinctive approach to organizing reusable functionality. I don't mean to dismiss it as uninteresting. I mean to set it aside as orthogonal to the "mutable state" consideration that seems to to be one of the central differences between OOP and FP.

In response to the request: "No. I won't map mindset to paradigm."

Lamenting the Death of Object-Oriented Programming. (Sigh) Again?

See Goodbye, Object Oriented Programming.

I don't want to say that the entire article is bunk. It's not. It raises a few good points. Points which I thought were pretty well known.

What's aggravating is that this lamentation is overly broad.  It treats all languages as if they're Java or C++. That's not true, and as a consequence, the article is less useful than it could be.

Banana Monkey Jungle Problem. Only true if you are sadly mistaken about the unit of reuse. The class as unit of reuse -- across projects -- is false, has been false, and will always be false. The idea of class inheritance for reuse makes perfect sense. Sharing individual classes between projects has never (as far as I know) been a promise of OO programming. Maybe I read the wrong books and missed that promise.

The Triangle Problem. Isn't actually a problem. Python has a defined method resolution order.

The Fragile Base Class Problem. This points out the well known issue with having concrete classes depend on other concrete classes. The SOLID design principles suggest concrete classes should depend on abstractions. Abstractions do not suffer (as much) from the fragile base class problem.

The Hierarchy Problem. I guess the idea that the real world is multi-dimensional can be confusing. If everything has to be force-fit into single inheritance, this would create the hierarchy problem. If we allow multiple inheritance, this problem evaporates.

The Reference Problem. Even C++ has "smart" pointer packages. Java has garbage collection. Python does reference counting. This is only a problem if you go out of your way to deal with pointers in a primitive way.

The part on Polymorphism didn't make any sense. There didn't seem to be a tidy problem. Just a confusingly vague statement that "Interfaces will give you [polymorphism?]. And without all of the baggage of OO". I don't get how interfaces are necessary without the baggage of OO. So, I can't really try to refute this.

In the long run, I guess this was a way to introduce some of the benefits of a functional approach. I'm not sure that this kind of criticism of object-oriented programming is very helpful. It doesn't apply to all OO languages, so it's misleading at best. (At worst, it's simply wrong.)

I think these problems are interesting and can be used to show the benefits of functional programming. But without the actual functional programming examples, this isn't very useful.

Getting Rid of the Gang-of-Four Design Patterns is Nonsense

Someone found Yet Another Post (YAP™) insisting that the Gang of Four (GOF™) patterns were on their last legs. The email was misleading, because this is not precisely what the article said. The bottom-line was that Design Patterns in general are merely a response to gaps in the underlying programming language. A position that's nonsense at its very foundation.

The lexicon of design patterns varies from language to language. GoF patterns aren't "going away." They're part of the Java/C++ world. They don't apply quite the same way to Python or functional languages.

There's a more serious issue, though: Language Mapping. First some background.

Design Patterns

Design Patterns will always exist. They're an artifact of how we process the world. We tend to classify individual objects so that we don't have to deal with each object as a separate wonder of nature.

It's Just Another Brick In The Wall.

We don't have to examine each rectangular solid of ceramic and understand the wonderfulness of it. We can group and summarize. Classify. Brick is a design pattern. So is masonry. So is wall. They're all patterns. It's how we think.

Design Patterns and Language Gaps

There's a claim that moving toward functional languages will kill design patterns. This presumes (partly) that non-OO languages magically don't have design patterns. This is (see above) kind of insane. Languages have design patterns. We recognize these patterns all the time.

A functional language has a common technique (or pattern) for visiting nodes in a hierarchy. We don't dwell on the wonderfulness of the code as if we'd never seen it before. Instead, we classify it based on the design pattern, and leverage this higher-level understanding to figure out why we're walking a hierarchy.

Sounding the death knell for design patterns also presumes (partly) that functional languages are magically more complete that OO languages. In this newer better language, we don't need patterns because there are no gaps. This is pretty much nutso, too. The Patterns Fill Language Gaps school of thought ignores the fact that there are many ways to implement these "gaps". We can use GoF design patterns, or we can use other software designs that don't fit the GoF design patterns. Both work.

The patterns aren't filling a "gap." They're providing guidance on how to implement something. That's all. Nothing more. Guidance.

"But wait," you say, "since I needed to write code, that's evidence that there's a gap."

"What?" I ask, incredulous. "Are you claiming that any code is evidence of a language gap? Does that mean all application software is just a language gap?"

"Let's not be silly," you say. "I can split a hair and create a tiny distinction between software I shouldn't have to write and software I should have to write."

I remain incredulous.

Design Patterns as Damage

The idea that somehow the GoF design patterns are a problem is also goofy. The GoF design patterns are pretty slick. They solve a fairly broad suite of problems in an elegant and consistent manner.

They're just good design.

Yes, they can be complex. Sorry about that. Software can be complex if you want really excellent flexibility and extensibility.

AND.

Bonus.

Software can be complex when you have to work around the problems of "compiler" and "locked libraries" and "no source." That is, the GoF patterns apply in full force for C++ and Java where you're trying to protect your intellectual property by disclosing only headers and obfuscated implementation details. Indeed, there are few alternatives to the GoF patterns if you're going to distribute a framework that has no visible source and needs to leave extension points for users.

If you don't have Locked-NoSource-Compiled code as a backdrop, the GoF patterns can be simplified a little. But some of the patterns are essential. And remain essential. There are some really great ideas there.

In Python world, we rely on a modified subset of the GoF patterns. They work extremely well.

When writing functional-style Python using immutable data structures (to the extent possible), we use a different set of design patterns. Not so many GoF patterns when we're trying to avoid stateful objects. But some patterns (like the Abstract Factory) are really very helpful even in a largely functional context. It morphs from an abstract factory class to a factory function, and it loses the "abstract" concept that's part of C++ and Java, but the core Factory design pattern remains.

The Serious Issue

The serious issue that is surfaced by the email is Language Mapping. We cannot (and must not) try to map languages to each other. What is true for Java design is emphatically not true for Python design. And it doesn't apply to assembly languages, FORTRAN, FORTH, or COBOL.

Languages are different.

There. I said it.

If there was an underlying "universal deep structure" behind all programming languages, the surface features would be merely syntax, and we'd have automated translation among languages. The universal deep structure (the underlying Turing Machine that does computations) appears to be too abstract to map well among programming languages. Hence the lack of translators.

When switching among languages, it's important to leave all baggage behind.

When moving from Java < 8 to Java >= 8<8 java="" to=""> (i.e., non-functional Java to more functional Java) we can't trivially map all design patterns among the language features. It's a new language with new features that happens to be compatible with the old language.

Attempting to trivially map concepts between non-functional (or strictly-OO Java) and more functional Java leads to dumb conclusions. Like the GoF patterns are dying. Or the GoF patterns represent damage or something else equally goofy.

The language changes lead to design pattern changes.

Language change doesn't deserve an gleeful/anguished blog post celebrating/lamenting the differences. It's a consequence of learning a new language, or new features of an existing language.

Please avoid mapping languages to each other.

Exploratory Data Analysis in Functional-Style Python

Here are some tricks to working with log file extracts. We're looking at some Enterprise Splunk extracts. We can fiddle around with Splunk, trying to explore the data. Or we can get a simple extract and fiddle around with the data in Python.

Running different experiments in Python seems to be more effective than trying to do this kind of exploratory fiddling in Splunk. Primarily because there aren't any boundaries on what we can do with the data. We can create very sophisticated statistical models all in one place.

Theoretically, we can do a lot of exploration in Splunk. It has a variety of reporting and analytical features.

But...

Using Splunk presumes we know what we're looking for. In many cases, we don't know what we're looking for: we're exploring. We may have some indication that a few RESTful API transactions are slow, but little more than that. How do we proceed?

Step one is to get raw data in CSV format. Now what?

Reading Raw Data

We'll start by wrapping a CSV.DictReader object with some additional functions.

Object-Oriented Purists will object to this strategy. "Why not just extend DictReader?" they ask. I don't have a great answer. I lean toward functional programming and the resulting orthogonality of components. With a purely OO approach, we have to use more complex-seeming mixins to achieve this.

Our general framework for processing logs is this.

with open("somefile.csv") as source:
    rdr = csv.DictReader(source)

This allows us to read the CSV-formatted Splunk extract. We can iterate through rows in the reader. Here's trick #1. It's not really very tricky, but I like it.

with open("somefile.csv") as source:
    rdr = csv.DictReader(source)
    for row in rdr:
        print( "{host} {ResponseTime} {source} {Service}".format_map(row) )

We can -- to a limited extent -- report raw data in a helpful format. If we want to dress up the output, we can change the format string. Maybe "{host:30s} {ReponseTime:8s} {source:s}" or something like that.

Filtering

A common situation is that we've extracted too much, and only need to see a subset. We can change the Splunk filter, but, we hate to overcommit before we've finished our exploration. It's far easier to filter in Python. Once we've learned what we need, we can finalize in Splunk.

with open("somefile.csv") as source:
    rdr = csv.DictReader(source)
    rdr_perf_log = (row for row in rdr if row['source'] == 'perf_log')
    for row in rdr_perf_log:
        print( "{host} {ResponseTime} {Service}".format_map(row) )

We've injected a generator expression that will filter the source rows, allowing us to work with a meaningful subset.

Projection

In some cases, we'll have additional columns of source data that we don't really want to use. We'll eliminate this data by making a projection of each row.

In principle, Splunk never produces an empty column. However, RESTful API logs may lead to data sets with a huge number of unique column titles based on surrogate keys that are part of request URI's. These columns will have one row of data from the one request that used that surrogate key. For every other row, there's nothing useful in that column. Life is much simpler if we remove the empty columns from each row.

We can do this with a generator expression, also, but it gets a bit long. A generator function is somewhat easier to read.

def project(reader):
    for row in reader:
        yield {k:v for k,v in row.items() if v}

We've built a new row dictionary from a subset of the items in the original reader. We can use this to wrap the output of our filter.

with open("somefile.csv") as source:
    rdr = csv.DictReader(source)
    rdr_perf_log = (row for row in rdr if row['source'] == 'perf_log')
    for row in project(rdr_perf_log):
        print( "{host} {ResponseTime} {Service}".format_map(row) )

This will reduce the unused columns that are visible in the inside of the for statement.

Notation Change

The row['source'] notation will get clunky. It's much nicer to work with a types.SimpleNamespace than a dictionary. This allows us to use row.source.

Here's a cool trick to create something more useful.

rdr_ns = (types.SimpleNamespace(**row) for row in reader)

We can fold this into our sequence of steps like this.

with open("somefile.csv") as source:
    rdr = csv.DictReader(source)
    rdr_perf_log = (row for row in rdr if row['source'] == 'perf_log')
    rdr_proj = project(rdr_perf_log)
    rdr_ns = (types.SimpleNamespace(**row) for row in rdr_proj)
    for row in rdr_ns:
        print( "{host} {ResponseTime} {Service}".format_map(vars(row)) )

Note the small change to our format_map() method. We've added the vars() function to extract a dictionary from the attributes of a SimpleNamespace.

We could write this as a function to preserve syntactic symmetry with other functions.

def ns_reader(reader):
    return (types.SimpleNamespace(**row) for row in reader)

Indeed, we could write this as a lambda construct which is used like a function.

ns_reader = lambda reader: (types.SimpleNamespace(**row) for row in reader)

While the ns_reader() function and ns_reader() lambda are used the same way, it's slightly harder to write a document string and doctest unit test for a lambda. For this reason, a lambda should probably be avoided.

We can use map(lambda row: types.SimpleNamespace(**row), reader). Some folks prefer this over the generator expression.

We could use a proper for statement with an internal yield statement, but there doesn't seem to be any benefit from making a big statement out of a small thing.

We have a lot of choices because Python offers so many functional programming features. We don't often see Python touted as a functional language. Yet, we have a variety of ways to handle a simple mapping.

Mappings: Conversions and Derived Data

We'll often have a list of data conversions that are pretty obvious. Plus, we'll have a growing list of derived data items. The derived items will be dynamic and are based on different hypotheses we're testing. Each time we have an experiment or question, we might change the derived data.

Each of these steps: filtering, projection, conversions, and derivation, are stages in the "map" portion of a map-reduce pipeline. We could create a number of smaller functions and apply them with map(). Because we're updating a stateful object, we can't use the general map() function.  If we wanted to achieve a more pure functional programming style, we'd use an immutable namedtuple instead of a mutable SimpleNamespace.

def convert(reader):
    for row in reader:
        row._time = datetime.datetime.strptime(row.Time, "%Y-%m-%dT%H:%M:%S.%F%Z")
        row.response_time = float(row.ResponseTime)
        yield row

As we explore, we'll adjust the body of this conversion function. Perhaps we'll start with some minimal set of conversions and derivations. We'll extend this with some "are these right?" kind of things. We'll take some out when we discover that the don't work.

Our overall processing looks like this:

with open("somefile.csv") as source:
    rdr = csv.DictReader(source)
    rdr_perf_log = (row for row in rdr if row['source'] == 'perf_log')
    rdr_proj = project(rdr_perf_log)
    rdr_ns = (types.SimpleNamespace(**row) for row in rdr_proj)
    rdr_converted = convert(rdr_ns)
    for row in rdr_converted:
        row.start_time = row._time - datetime.timedelta(seconds=row.response_time)
        row.service = some_mapping(row.Service)
        print( "{host:30s} {start_time:%H:%M:%S} {response_time:6.3f} {service}".format_map(vars(row)) )

Note that change in the body of our for statement. Our convert() function produces values we're sure of. We've added some additional variables inside the for loop that we're not 100% sure of. We'll see if they're helpful (or even correct) before updating the convert() function.

Reductions

When it comes to reductions, we can adopt a slightly different style of processing. We need to refactor our previous example, and turn it into a generator function.

def converted_log(some_file):
    with open(some_file) as source:
        rdr = csv.DictReader(source)
        rdr_perf_log = (row for row in rdr if row['source'] == 'perf_log')
        rdr_proj = project(rdr_perf_log)
        rdr_ns = (types.SimpleNamespace(**row) for row in rdr_proj)
        rdr_converted = convert(rdr_ns)
        for row in rdr_converted:
            row.start_time = row._time - datetime.timedelta(seconds=row.response_time)
            row.service = some_mapping(row.Service)
            yield row

We've replace the print() with a yield.

Here's the other part of this refactoring.

for row in converted_log("somefile.csv"):
    print( "{host:30s} {start_time:%H:%M:%S} {response_time:6.3f} {service}".format_map(vars(row)) )

Ideally, all of our programming looks like this. We use a generator function to produce data. The final display of the data is kept entirely separate. This allows us to refactor and change the processing much more freely.

Now we can do things like collect rows into Counter() objects, or perhaps compute some statistics. We might use a defaultdict(list) to group rows by service.

by_service= defaultdict(list)
for row in converted_log("somefile.csv"):
    by_service[row.service] = row.response_time
for svc in sorted(by_service):
    m = statistics.mean( by_service[svc] )
    print( "{svc:15s} {m:.2f}".format_map(vars()) )

We've decided to create concrete list objects here. We can use itertools to group the response times by service. It looks like proper functional programming, but the implementation points up some  limitations in the Pythonic form of functional programming. Either we have to sort the data (creating a list object) or we have to create lists as we group the data. In order to do several different statistics, it's often easier to group data by creating concrete lists.

Rather than simply printing a row object, we're now doing two things.

1. Create some local variables, like svc and m. We can easily add variance or other measures.
2. Use the vars() function with no arguments, which creates a dictionary out of the local variables.

This use of vars() with no arguments -- which behaves like locals() -- is a handy trick. It allows us to simply create any local variables we want and include them in the formatted output. We can hack in as many different kinds of statistical measures as we think might be relevant.

Now that our essential processing loop is for row in converted_log("somefile.csv"), we can explore a lot of processing alternatives in a tiny, easy-to-modify script. We can explore a number of hypotheses to determine why a some RESTful API transactions are slow and others are fast. 

Functional Python Programming

New from Packt Publishing: Functional Python Programming.

Also here on Amazon.

The fun part is covering generator functions, iterators, and higher-order functions in some real depth. There's a lot of powerful programming techniques available.

What's challenging is reconciling Python's approach to FP with languages that are purely functional like Haskell and OCaml and others. Years ago, I saw some discussion in Stack Overflow that Python simply wasn't a proper functional programming language because it lacked some features. I'm vague on specifics (perhaps there weren't any) but the gaps between Python and FP are narrow.

As far as I can tell, the single biggest features missing are non-strict evaluation coupled with an optimizer that can rearrange expressions to optimize performance. This feature pair also tends to also produce nice tail-call optimization of recursions.

Languages which are totally non-strict (or fully lazy) need to introduce monads so that some ordering can be enforced in the cases where ordering really does matter.

Since Python is strict (with only minor exceptions) monads aren't needed. But we also sacrifice some optimization capability because we can't reorder Python's strict expressions. I'm not sure this is a gap which is so huge that we can indict Python as being non-functional or not suitable for a functional approach. I think the lack of an optimizing compiler is a little more than an interesting factoid.

An interesting problem that compiled functional languages have is resolving data types properly. It's a problem that all statically-typed languages share. In order to write a really generic algorithm, we either have to rely on a huge type hierarchy or sophisticated type pattern-matching rules. Python eschews this problem by making all code generic with respect to type. If we've applied a function to an inappropriate object, we find out through unit testing that we have TypeError exceptions.

I think we can (and should) borrow functional programming design patterns and reimplement them in Python. This is quite easy and doesn't involve too much work or overhead. For example, the yield from statement allows us to do manual tail-call optimization rather than trusting that the compiler will recognize the code pattern.

Chapter 12 Alternate Example - Normalization and Decorators

In the forthcoming Functional Python Programming (https://www.packtpub.com/application-development/functional-python-programming) I was pressured by one of the technical reviewers to create a better example of composite function creation with decorators.

This was a difficult request. First, of course, "better" is poorly defined. More importantly, the example in the book is extensive and includes the edge-of-the-envelope "don't do this in real code" parts, too. It's important to be thorough. Finally, it's real-world data cleansing code. It's important to be pragmatic, but, it's kind of boring. I really do beat it into submission showing simple decorators, parameterized decorators, and crazy obscurely bad decorators.

In this case, "better" might simply mean "less thorough."

But, perhaps "better" means "less focused on cleansing and more focused on something else."

On Decoration

The essence of the chapter -- and the extensive example -- is that we can use decorators as higher-order functions to build composite functions.

Here's an alternative example. This will combine z-score normalization with another reduction function. Let's say we're doing calculations that require us to normalize a set of data points before using them in some reduction.

Normalizing is the process of scaling a value by the mean and standard deviation of the collection. Chapter 4 covers this in some detail. Reductions like creating a sum are the subject of Chapter 6. I won't rehash the details of these topics in this blog post.

Here's another use of decorators to create a composite function.

def normalize( mean, stdev ):
    normalize = lambda x: (x-mean)/stdev
    def concrete_decorator( function ):
        @wraps(function)
        def wrapped( data_arg ):
            z = map( normalize, data_arg )
            return function( z )
        return wrapped
    return concrete_decorator

The essential feature of the @normalize(mean, stdev) decorator is to apply the normalization to the vector of argument values to the original function. We can use it like this.

>>> d = [ 2, 4, 4, 4, 5, 5, 7, 9 ]
>>> from Chapter_4.ch04_ex4 import mean, stdev
>>> m_d, s_d =  mean(d), stdev(d)
>>> @normalize(m_d, s_d)
>>> def norm_list(d):
...     return list(d)
>>>
>>> norm_list(d)
[-1.5, -0.5, -0.5, -0.5, 0.0, 0.0, 1.0, 2.0]

W've create a norm_list() function which applies a normalization to the given values. This function is a composite of normalization plus list().

Clearly, parts of this are deranged. We can't even define the norm_list() function until we have mean and standard deviation parameters for the samples. This doesn't seem appropriate.

Here's a slightly more interesting composite function. This combines normalization with sum().

>>> @normalize(m_d, s_d)
>>> def norm_sum(d):
...     return sum(d)
>>>
>>> norm_sum(d)
0.0

We've defined the normalized sum function and applied it to a vector of values. The normalization has parameters applied. Those parameters are relatively static compared with the parameters given to the composite function.

It's still a bit creepy because we can't define norm_sum() until we have the mean and standard deviation.

It's not clear to me that a more mathematical example is going to be better. Indeed, the limitation on decorators seems to be this:

• The original (decorated) function can have lots of parameters;
• The functions being composed by the decorator must either have no parameters, or have very static "configuration" parameters.

If we try to compose functions in a more general way -- all of the functions have parameters -- we're in for problems. That's why the data cleansing pipeline seems to be the ideal use for decorators.

Wow. Two-Word Question. Profound Insight.

I'm working on yet another Python book. This one looking at functional programming in Python. It doesn't really go with with Mastering Object-Oriented Python and Python for Secret Agents because the focus isn't on Python's strong suit.

In chapter one, a reviewer had this two-word question:

"yield from?"

What? What does "yield from" mean?

Oh.

Wow.

https://docs.python.org/3/whatsnew/3.3.html#pep-380-syntax-for-delegating-to-a-subgenerator

I had utterly missed this profound, important feature.

I guess I have been too blasé in skimming the release notes.

That's embarrassing.  And it only took two words to reveal my mistake.

I had to then review all 113 yield statements in 72 files of examples that go with the book.  That means most chapters will get touched to revise an example to show yield from iter instead of the older for x in iter: yield x template.

This also changes the Tail Call Optimization material. The explicit for was actually kind of nice for showing how TCO is implemented in Python. The yield from makes it a little less clear.

Some reviewers consider TCO so fundamental that it belongs in chapter 1. The omission of detailed analysis of Python's TCO approach was considered a significant flaw. Other reviewers seemed happy setting discussion of TCO aside for later.

The Functional Python Conundrum

This book is going to be difficult. The ratings from the reviewers were low. Really low. It looks like I've got a lot of work to do. Finding the target audience will be difficult.

One reviewer asked -- in effect -- why would someone who knew functional LISP ever use Python? I don't think there's a big audience of disgruntled LISP programmers, so that's not a relevant question.

Viewed from the other direction, it's hugely import. Why would a Python programmer adopt functional design patterns? That's the question that needs to be answered clearly.

And from the reviews of chapter 1, it wasn't addressed clearly enough.

Declarative Programming

I know that some folks swear by declarative programming. They like the ideas behind ant (and make) and SCons and related examples.

You can google for "ant v. maven v. gradle" where people gripe about which is more declarative. The point of the whining being that more declarative == good and any traces of procedural or imperative programming == bad.

All, of course, without any really good justification of why declarative is better. It's assumed that declarative simply has innumerable advantages. And yes, I've started with http://en.wikipedia.org/wiki/Declarative_programming. The issue isn't simply moot; the justification is weak.

Perhaps there's a awful bias toward imperative and functional programming. After all, the big thinkers in computer science tend to favor the imperative and functional schools of thought. Maybe declarative suffers from some bias.

Or maybe declarative has limited utility.

There. I said it. Limited utility.

I think a functional approach might be better, faster and simpler.

Side-bar Ranting

The code is below. You can skip down to the "The Functional Build System" section and not miss much.

Declarative programming seems applicable to the cases where the ordering of operations can be easily deduced. It seems like the significant value of declarative programming is to rely on an optimizing compiler rearrange the declarations into properly-ordered imperative steps. From this viewpoint, it seems like ant/maven/gradle are optimizers that look at the dependencies among transformation functions and then apply the functions in the proper order.

It seems like we're writing expressions like these:

x.class = java(x.java)
xyz.jar = jar(x.class, y.class, z.class, ... )
app.war = war(xyz.jar, abc.jar, ... )

and then turning them over to a clever compiler (like Haskell) to work out a total order among the expressions that will build the right thing for us.

There's a potential difference between manually structuring a script to get all of the steps in order and allowing the compiler to arrange things properly based on some formal semantics behind each expression.

It's a potential difference because most folks that deal with ant/maven/gradle tend to put things in more-or-less the right order so that others can figure out what the hell is going on. In the trivial cases where we're building simple web sites, the default rules have evolved to the point where they work in almost all cases, so we don't even look at the configuration of the tools. We hit Ctrl+B knowing that it's all setup properly

Some Requirements

A number of applications have ant-like (or make-like) aspects but don't really cry out for ant with customized actions. We might be doing data warehouse loads which involve an ant-like sequence of processing steps to do transformations, loads, and produce final summaries and confirmations. We can, of course, write this all in first-class Java code. The hard way.

It's not terribly complex. A class to define a dependency. A suite of plug-in strategies. Some static definitions of the actual rules. Been there. Done that.

Pragmatically, the declarative style suffers from a limitation of being rather rigid in applying a fixed set of rules. A more script-like implementation can be more helpful to support reruns, debugging, problem-solving and the inevitable special cases and exceptions. After a storage failure -- and the reruns required to get the warehouse back up-to-date -- one sees more need for script-like flexibility and less need for overly simplistic rigidity.

Another end of the spectrum is individual steps all manually coordinated with a tool like BMC's Control-M. This requires endless manual intervention to make sure all the various tasks are defined properly in Control-M.

Somewhere near the middle is a configurable application with some processing rules to give it flexibility. But some defined structure to remove the need for carefully planned manual intervention and deep expertise.

The Functional Build System

We can image an ant-like build system defined functionally.

The core is a function that implements build-if-needed rules:

def build_if_needed( builder, target_file, *source ):
    if target_ok( target_file, *source ):
        return "ok({0},...)".format(target_file)
    builder( target_file, *source )
    return "{0}({1},...)".format(builder.__class__.__name__,target_file)

We can use this function to define the essential dependency: use a builder function to create some target if it's out-of-date with respect to the sources. The return value forms a kind of audit log.

This relies on some helper functions: target_ok() checks the modification times of files. The various builders do the various kinds of operations required to make one from the sources.

Here's the target_ok() function

def target_ok( target_file, *source_list, logger=logging ):
    try:
        mtime_target= datetime.datetime.fromtimestamp(
            os.path.getmtime( target_file ) )
    except Exception:
        return False
    # If a source doesn't exist, we throw an exception.
    times = (datetime.datetime.fromtimestamp(
            os.path.getmtime( source ) ) for source in source_list)
    return all(mtime_target > mtime_source for mtime_source in times)

I think this function is what started me thinking about a functional approach. It could be a method of a class. But. It's seems like a very functional design. It could be reduced to a single (long) expression.

The builders are composite functions. They need to combine the subprocess.check_call() with a function that builds the command. We can do functional composition several ways in Python: we can combine functions via decorators. We can also combine functions via Callables. We could write a higher-order function that combines the check_call() with a function to create the command.

We'll opt for the higher-order function and create partially evaluated forms using functools.partial().

Here's a typical case:

def subprocess_builder( make_command, target_file, *source_list ):
    command= make_command( target_file, *source_list )
    subprocess.check_call( command )

This is a generic function: it requires a function (or lambda) to build the actual command. We might do something like this to create a specific builder.

def command_rst2html( output, *input ):
        return ["rst2html.py", "--syntax-highlight=long", "--input-encoding=utf-8", input[0], output]

rst2html= partial( subprocess_builder, command_rst2html )

This rst2html() function can be used to define a dependency rule. We might have something like this:

    files_txt = glob.glob( "*.txt" )
    for f in files_txt:
        build_if_needed( rst2html, ext_to(f,'.html'), f )

This rule specifies that *.html files depend on *.txt files; when needed, use the rst2html() function to build the required html file when the txt file is newer.

The ext_to() function is a two-liner that changes the extension on a filename. This helps us write "template" build rules rather than exhaustively enumerating a large number of similar files.

def ext_to( filename, new_ext ):
    name, ext = os.path.splitext( filename )
    return name + new_ext

What we've done here is define a few generic functions that form the basis for a functional build system that can compete against ant, make or scons. The system is not even close to declarative. However, we only need to assure that our final build_if_needed() functions have a sensible ordering, something that's rarely a towering intellectual burden.

The individual customizations are the build commands like rst2html() where we created the command-line list of strings for subprocess.check_call(). We can just as easily build functions which run entirely in the process or functions which farm the work out to separate processes via queues or RESTful web services.

Bottom Lines

It appears that declarative programming isn't terribly helpful. There may be a niche, but it seems to be a small niche to me.

I'm sure that an object-oriented approach to this problem isn't any better. I've written a shabby-make version of this, and it's bigger. There's just more code and it's not significantly more clear what's going on. Inheritance can be difficult to suss out.

Python seems to be a good functional programming language. It did this very nicely.

Currying and Partial Function Evaluation

Old. But still interesting.

Partial Function Application is not Currying

It seems like hair-splitting. However, the distinction between bound variables and curried functions does have some practical implications.

I'm looking closely at PyMonad and the built-in functools library.

I'm finding some benefits in understanding functional programming and how to apply functional design patterns in Python. I'm also seeing the important differences between compiled -- and optimized languages -- and Python's approach. I'm slowly coming to understand how a (simple) recursive design is flattened into a for loop as part of manual tail-recursion optimization.

The functional programming goodness is giving me first-class headaches when trying to apply the lessons learned to Java, however. I suppose I should look closely at http://www.functionaljava.org and https://code.google.com/p/functionaljava/. There are claims that it's dangerously inefficient. Also, the customer who insists on Java has a (very) limited set of allowed libraries; if this isn't on the list, then the whole concept is a non-starter.

Enriched Details of Apache Common Log Format

See Apache Log Parsing for the background.

Here's a generator function which expands a simple Access to be a more detailed named tuple.

Access_Details= namedtuple( 'Access_Details',
    ['access', 'time', 'method', 'url', 'protocol'] )
            
def details_iter( iterable ):
    def parse_time_linux( ts ):
        return datetime.datetime.strptime( ts, "%d/%b/%Y:%H:%M:%S %z" )

    def parse_time_macos( ts ):
        dt= datetime.datetime.strptime( ts[:-6], "%d/%b/%Y:%H:%M:%S" )
        tz_text= ts[-6:]
        sign, hh, mm = tz_text[:1], int(tz_text[1:3]), int(tz_text[3:])
        minutes= (hh*60+mm) * (-1 if sign == '-' else +1)
        offset = datetime.timedelta(minutes = minutes)
        tz= datetime.timezone( offset, tz_text )
        return dt.replace(tzinfo=tz)
        return dt

    first, last = None, None
    for access in iterable:
        meth, uri, protocol = access.request.split()
        dt= parse_time_macos( access.time )
        first= min(dt,first) if first else dt
        last= max(dt,last) if last else dt
        yield Access_Details(
            access= access,
            time= dt,
            method= meth,
            url= urllib.parse.urlparse(uri),
            protocol= protocol )

    print( "Log Data from", first, "to", last, 'duration', last-first )

This "wraps" the original Access object with an Access_Details that includes information that isn't trivially parsed from the access row.

• The datetime object with the real timestamp.  Not the Mac OS subtlety.  Due to platform issues, the %z strptime format doesn't seem to work in Python 3.2
• The three fields from the request: method, URL and protocol.  
• The URL is parsed into its individual fields.

Note that the Access_Details object is pickle-able.  While seemingly irrelevant, it turns out that having something which can be pickled means that we can use multiprocessing to create a multi-staged concurrent pipeline of log analysis.

What's important here is that we're adding functionality without redefining the underlying Access class. Indeed, the underlying Access object is immutable.  The idea of stateless values comes from the functional programming crowd.  It seems to work out really well because the functionality seems to accrete in relatively simple layers.

Apache Log Parsing

How much do I love Python?  Consider this little snippet that parses Apache logs.

import re
from collections import defaultdict, named tuple

format_pat= re.compile( 
    r"(?P<host>[\d\.]+)\s" 
    r"(?P<identity>\S*)\s" 
    r"(?P<user>\S*)\s"
    r"\[(?P<time>.*?)\]\s"
    r'"(?P<request>.*?)"\s'
    r"(?P<status>\d+)\s"
    r"(?P<bytes>\S*)\s"
    r'"(?P<referer>.*?)"\s' # [SIC]
    r'"(?P<user_agent>.*?)"\s*' 
)

Access = namedtuple('Access',
    ['host', 'identity', 'user', 'time', 'request',
    'status', 'bytes', 'referer', 'user_agent'] )

def access_iter( source_iter ):
    for log in source_iter:
        for line in (l.rstrip() for l in log):
            match= format_pat.match(line)
            if match:
                yield Access( **match.groupdict() )

That's about it.  The access log rows are now first-class Access-class objects that can be processed pleasantly by high-level Python applications.

Cool things.

1. The adjacent string concatenation means that the regular expression can be broken up into bits to make it readable.
2. When the named tuple attributes match the regular expression names, we can trivially turn the match.groupdict() into a named tuple. 
3. By using a generator, the other parts of the application can simply loop through the results without tying up memory to create vast intermediate structures.

A couple of years back, a sysadmin was trying to justify spending money on a log analyzer product.  I suggested they (at the very least) get an open source log analyzer.

I also suggested that they learn Python and save themselves the pain of working with a (potentially) complex tool.  Given this as a common library module, log analysis applications are remarkably easy to write.

Statically Typed Language Nonsense

Read this: "Here Comes Functional Programming" by Larry O'Brien in SD Times.

people who should know better continue to assert that statically typed languages are "safer, because the compiler can catch errors that otherwise wouldn't show up until runtime." While it's true a statically typed language can detect that you've assigned a string to a double without running your code, no type system is so strict that it can substitute for a test suite, and if you have a test suite, type-assignment errors are discovered and precisely diagnosed with little difficulty.

Thank you.   A language like Python, which lacks static type declarations for variables, is not evil or an accident waiting to happen.

The article is about functional languages.  But the static declaration statement is universally true.

Transformation Pipelines

My laptop chartplotter software (GPSNavX) is marvelous for visualizing a route. But, there are elements to route planning that it doesn't handle gracefully.

Specifically, it doesn't provide useful elapsed time calculation at all. While the TTG and ETA (Time to Go and Estimated Time of Arrival) for the next waypoint are essential, they aren't enough. On a sailboat, you need to know the complete sequence of planned arrival times so that you can gauge the overall impact of wind and tide vagaries on the trip.

As the trip progresses, the schedule variance allows informed decision-making. Tack? Hole up for the night? Motor?

GPSNavX has a number of marvelous export capabilities -- as GPX, KML or CSV data. These contain a list of waypoints and little more. We need to enrich this data to produce an overall schedule.

Enriching The Data

Fundamentally, we have a number of enrichment stages. The functional programming features of Python make this complex sequence of enrichment stages into a very tidy, and adaptable application.

    if variance is None: variance= chesapeake
with open(route_file,'rb') as source:
  rte= csv.reader(source)
  with open(schedule_file,'wb') as target:
      rte_rhumb= csv.writer( target )
      rte_rhumb.writerow(
          ["Name", "Lat", "Lon", "Desc",
          "Distance (nm)", "True Bearing", "Magnetic Bearing",
          "Distance Run", "Elapsed HH:MM", ]
          )
      for sched in gen_schedule( gen_mag_bearing( gen_rhumb( gen_route_points( rte ) ), variance), speed ):
          rte_rhumb.writerow(
              [sched.point.name, sched.point.lat, sched.point.lon, sched.point.desc,
              sched.distance,
              int(sched.true_bearing.deg) if sched.true_bearing is not None else None,
              int(sched.magnetic.deg) if sched.magnetic is not None else None,
              sched.running, sched.elapsed_hm, ]
              )

Essentially, the core of this is a simple composition of generator functions.

for sched in gen_schedule( gen_mag_bearing( gen_rhumb( gen_route_points( rte ) ), variance), speed ):

We have a number of individual transformations to look at. Each of those follows a common pattern. The transformations are:

• gen_route_points( rte )
• gen_rhumb( route_points_iter )
• gen_mag_bearing( rhumb_iter, declination )
• gen_schedule( rhumb_mag_iter, speed= 5.0 )

There's a bunch of fancy math involved in the rhumb line and distance between two points on the surface of the earth. For my purposes, plane sailing is fine. I don't need great circle routes because I'm not going far.

See Calculate distance, bearing and more between Latitude/Longitude points for a clear and useful treatment of the math. Bowditch's American Practical Navigator, chapter 24, provides alternate methods using table lookup and interpolation.

Seeding the Pipeline

Here, for example, is the first step of the pipeline. Creating a RoutePoint from the four values found in the CSV or GPX route file.

RoutePoint= namedtuple( 'RoutePoint', 'name,lat,lon,desc,point' )

def gen_route_points( rte ):
for name,lat,lon,desc in rte:
   point= navigation.LatLon( lat, lon )
   yield RoutePoint( name, lat, lon, desc, point )

Since this is a generator function, it can use an iterator and be used by an iterator. The source iterator can be a csv.reader. Or it can be the result of XML parsing -- just so long as it matches the interface specification of being an iterator over a 4-tuple.

Rhumb-Line Calculation

We'll enrich the data. But we won't update an object. We'll stick closely to the philosophy of immutable objects (i.e., named tuples) which are modified by a generator function.

RoutePoint_Rhumb= namedtuple( 'RoutePoint', 'point,distance,bearing' )

def gen_rhumb( route_points_iter ):
p1= route_points_iter.next()
for p2 in route_points_iter:
    r, theta= navigation.range_bearing( p1.point, p2.point )
    yield RoutePoint_Rhumb( p1, r, theta )
    p1= p2
yield RoutePoint_Rhumb( p2, None, None )

The essential calculations are in a separate module, navigation. What we've done, however, is merge information from adjacent values so that we can transform a simple list of points into a list of pairs of points: the from and to for each leg of the trip. Between the two points, we compute the simple rhumb line, the distance and bearing.

True to Magnetic Conversion

We need to enrich our waypoint rhumb-line information with magnetic compass information. The true course needs a declination or variance value added to it. Again, we're just creating new objects from existing objects, using immutable named tuples.

RoutePoint_Rhumb_Magnetic= namedtuple( 'RoutePoint', 'point,distance,true_bearing,magnetic' )

def gen_mag_bearing( rhumb_iter, declination ): # A/k/a Variation
 for rp_rhumb in rhumb_iter:
     if rp_rhumb.bearing is None:
         yield RoutePoint_Rhumb_Magnetic(rp_rhumb.point, None, None, None)
     else:
         magnetic= rp_rhumb.bearing+declination(rp_rhumb.point)
         yield RoutePoint_Rhumb_Magnetic(rp_rhumb.point, rp_rhumb.distance, rp_rhumb.bearing, magnetic )

In this case, we're simply including a declination calculation. While the model is available from IUGG, we can often use averages or approximations. And -- in the Chesapeake -- the approximation is simply to add 11 degrees.

Spot-on accuracy doesn't matter, since we're driving a sailboat. The compass isn't very accurate; the boat motion makes it hard to read precisely; and current as well as leeway have profound effects. It is helpful to have magnetic courses in the schedule instead of true courses. Further, the chartplotter will be computing the final CTS (Course to Steer).

So this stage in the pipeline might be optional.

Distance Run and Elapsed Time

The final distance run and elapsed time is pretty simple. We're creating a new tuple from existing tuples.

SchedulePoint = namedtuple( 'RoutePoint', 'point,distance,true_bearing,magnetic,running,elapsed_min,elapsed_hm' )

def gen_schedule( rhumb_mag_iter, speed= 5.0 ):
  distance = 0.0
  for rp in rhumb_mag_iter:
      if rp.true_bearing is None:
          yield SchedulePoint( rp.point, rp.distance, rp.true_bearing, rp.magnetic, None, None, None )
      else:
          distance += rp.distance
          elapsed_min= 60.*distance/speed
          h, m = divmod( int(elapsed_min), 60 )
          elapsed_hm = "{0:02d}h {1:02d}m".format( h, m )
          yield SchedulePoint( rp.point, rp.distance, rp.true_bearing, rp.magnetic, distance, elapsed_min, elapsed_hm )

This gives us a tuple that includes the original way point, the next waypoint, the distance, true bearing, magnetic bearing, total distance run, and elapsed time.

The amount of programming is minimal. The overall design seems reasonably flexible and built from small, easy-to-validate pieces.

Python's functional programming features -- particularly generator functions and named tuples -- seem to make it pleasant to write this kind of transformation pipeline.

Oracle Analytics and Functional Programming

As a hypothetical, I was asked about doing Oracle Analytic functions in Python.

[Sidebar: Politics. The question came from a DBA in a C# shop. That's why it's just hypothetical. Politically, they could never make use of this information. In C# world, Functional Programming is often scary and evil. It does exist -- obviously -- but it's called "Oracle Analytics", which makes it acceptable. If functional programming was called "functional programming" it would be unacceptable.]

[Sidebar: SQL. A big apples-to-oranges issue here is that the Oracle analytic functions can be composed in subqueries to write complex reporting queries. When you implement these functions in Python, you appear to lose some SQL "features" for report-writing. Actually, you move the SQL functional programming into Python functional programming. Everyone complains when they have to give up SQL. The true haterz say that using Python's functional programming for database processing subverts the database and leads to moral decay and the end of Western Civilization. Godwin's Law then applies.]

Specific functions lifted up to me were RANK, FIRST, LAST, ROW_NUMBER and DENSE_RANK. All of these are relatively simple functional programming examples.

GROUP BY

First -- and foremost -- SQL GROUP-BY can be slow. No one ever wants to hear this. The true haterz will claim that it's supposed to be faster and provide a bunch of non-reasons. Please benchmark.

Every database has to provide a GROUP-BY implementation that's perfectly general; it has to sort. A procedural program can sometimes do the same operation much more quickly because it doens't have to be perfectly general; we can make different memory use tradeoffs than the the database does.

For a fast GROUP-BY, use a hash map of some kind. Read all the rows in the simplest, fastest array fetch possible. Here's how you can do a blindingly fast SUM/GROUP-BY.

from collections import defaultdict

from decimal import Decimal

groups = defaultdict( Decimal )

for row in some_query_result_set:

groups[row['key']] += groups[row['value']]

Writing code like this is based on the assumption that the number of groups is small enough to fit into memory. That assumption allows us to avoid a sort. The database can't make this assumption, and can't easily use this kind of data structure.

Functional Programming

The analytical functions are nice applications of a functional style of programming. The ROW_NUMBER is already part of Python: it's the internal enumerate function.

We can use enumerate to implement FIRST.

def first( the_limit, some_query ):

for number, row in enumerate( some_query ):

if number >= the_limit:

break

yield row

This first function can be then used in another loop.

for row in first( 100, some_query ):

process( row )

LAST is more complex because there's no easy way to skip ahead. Instead we have to buffer some rows.

def last( the_limit, some_query ):

queue = []

for row in some_query:

if len(queue) == the_limit:

queue.pop( 0 )

queue.append( row )

for row in queue:

yield row

This can be sped up a little by using an explicit iterator object and breaking the `for row in some_query` loop into two phases to hoist the nearly-constant if-statement.

These can be composed with Python's sorted function.

for row in first( 10, sorted( some_query, key=lambda row: row['key'] ) ):

process( row )

This is elegant, but may only draw a tie in a race against the database. Python has the potential advantage of in-memory sorting. Oracle, however, is clever enough to use in-memory sorting on small sets of data, offsetting Python's advantage.

More Complex Functions

The more complex functions of RANK and DENSE_RANK require two-phase processing of rows. If we assume that we can fit the rows in memory, this isn't very complex at all. Indeed, the rank function is just a glorified order-by of a subset of the original data. However, it does require a potentially slow sort step.

ranked = enumerate ( sorted( some_query,

key = lambda row: row['key'] ) )

Okay. So RANK isn't so complex after all. Functional programming rocks.

DENSE_RANKED is confusing to me, but it look like the key phrase is "Rows with equal values for the ranking criteria receive the same rank." This means that the simple built-in enumerate isn't appropriate, and we need a key-aware enumeration.

def dense_rank( some_query, key ):

query_iter= iter(some_query)

rank= 1

current = query_iter.next()

yield rank, current

for row in query_iter:

if key(current) != key(row):

rank += 1

current= row

yield rank, row

Composition

One of the strong suits of SQL is that it allows us to define a functional-programming composition. Rather than write a lot of looping, we specify a series of functions which are composed and applied to our data.

For example, using FIRST and DENSE_RANK can be done like this.

for row in first( 10, dense_rank( some_ordered_query, key=lambda row: row['key'] ) ):

process( row )

This functional programming composition is -- BTW -- precisely what SQL specifies. SQL describes incremental processing of each row through a kind of pipeline that does map, filter, reduce and sort algorithms on the row.

The ORDER-BY clause is an initial sort.

The WHERE clause is an initial filter. It may involve a mapping if there are calculations in the various parts of the WHERE clause.

The GROUP-BY clause is a reduction into groups.

The HAVING clause is a second filter, applied to the groups. It may involve a mapping if there are calculations in the various parts of the HAVING clause.

Finally the SELECT clause is a mapping that does calculations on the resulting collection of rows.

The analytic functions, like subqueries, are simple complex mapping operations that involve other query pipelines.

Functional Programming Goodness -- Python to the Rescue

Here's the situation.

A vendor sent us three separate files which need to be merged. 70,000+ records each. They're CSV files, so column position doesn't much matter. The column name (in row 1) is what matters.

I looked at three solutions. Two of which are merely OK. The third was some functional programming that was very cool.

Option 1 -- OS Sort/Merge

To get the files into a consistent order, we need to sort. The Linux sort, however, is biased toward columns that are known positionally.

So, we need to exploit the Decorate-Sort-Undecorate design pattern. So we have a shell script something like the following.

decorate.py a.csv | sort >a_sorted.csv
decorate.py b.csv | sort >b_sorted.csv
decorate.py c.csv | sort >c_sorted.csv
sort -m a_sorted.csv b_sorted.csv c_sorted.csv | undecorate.py >result.csv

This works well because decorate.py and undecorate.py are such simple programs. Here's decorate.py.

from __future__ import print_function
import csv
import sys
with open(sys.argv[1],"rb") as source:
rdr= csv.DictReader( source )
for row in rdr:
  print( row['the key'], row )

Undecorate is similar. It uses the str.partition() method to remove the decoration.

Note that the initial "decorate" steps can be run concurrently, leading to some time reduction. This scales well. It doesn't use much memory; the OS concurrency management means that it uses every core available.

I didn't benchmark this, BTW.

Option 2 -- Big In-Memory Dict

Since the files aren't insanely big, they do fit in memory. This is pretty simple, also.

import csv
from collections import defaultdict
# build the result set
result = defaultdict( dict )
for f in ( 'a.csv', 'b.csv', 'c.csv' ):
with open( f, 'rb' ) as source:
  rdr = csv.DictReader( source )
  for row in rdr:
      result[row['key']].update( row )
# find the column titles
keys = set()
for row in result:
  keys |= set( result[row].keys() )
# write the result set
with open( 'output.csv', 'wb' ) as target:
  wtr= csv.DictWriter( target, sorted(keys) )
  wtr.writerow( dict(zip(keys,keys)) )
  for row in result:
      wtr.writerow( result[row] )

This isn't too bad. For insanely big files, however, it won't scale well.

Elapsed time for the real files (which were zipped, adding processing that's not relevant to this posting) was 218 seconds on my little laptop.

Option 3 -- Functional Programming

The functional programming approach is a bit more code than option 1. But it's way cool and very extensible. It offers more flexibility without the memory limitation of the big dictionary.

Let's start with the end in mind.

We're doing a 3-file merge. The algorithm for 2-file merge is really simple. The algorithm for an n-file merge, however, is not so simple. We can easily build up an n-file merge as a composition of n-1 pair-wise merges.

Here's how it should look.

with open('temp.csv','wb') as output:
  wtr= csv.DictWriter( output, sorted(fieldNames) )
  wtr.writerow( dict( zip( fieldNames, fieldNames )))
  for row in merge( merge( s1, s2 ), s3 ):
      wtr.writerow( row )

We're doing merge( merge( s1, s2 ), s3 ) to compose a 3-file merge from 2 2-file merges. And yes, it can be just that simple.

Composable Sort

To be "composable", we must write iterator functions which read and write data of the same type. In our case, since we're using a DictReader, our various functions must work with an iterable over dicts which yields dicts.

In order to merge, the input must be sorted. Here's our composable sort.

def key_sort( source, key='key' ):
  def get_key( x ):
     return int(x[key])
  for row in sorted(source, key=get_key ):
     yield row

Yes, we need to pre-process the keys, they're not simple text; they're numbers.

Composable 2-File Merge

The composable merge has a similar outline. It's a loop over the inputs and it yields outputs of the same type.

def merge( f1, f2, key='key' ):
"""Merge two sequences of row dictionaries on a key column."""
r1, r2 = None, None
try:
r1= f1.next()
r2= f2.next()
while True:
    if r1[key] == r2[key]:
        r1.update(r2)
        yield r1
        r1, r2 = None, None
        r1= f1.next()
        r2= f2.next()
    elif r1[key] < r2[key]:
        yield r1
        r1= None
        r1= f1.next()
    elif r1[key] > r2[key]:
        yield r2
        r2= None
        r2= f2.next()
    else:
        raise Exception # Yes, this is impossible
except StopIteration:
    pass
if r1 is not None:
    yield r1
    for r1 in f1:
       yield r1
elif r2 is not None:
    yield r2
    for r2 in f2:
        yield r2
else:
    pass # Exhausted with an exact match.

This runs in 214 seconds. Not a big improvement in time. However, the improvement in flexibility is outstanding. And the elegant simplicity is delightful. Having the multi-way state managed entirely through the Generator Function/Iterator abstraction is amazing.

Also, this demonstrates that the bulk of the time is spent reading the zipped CSV files and writing the final CSV output file. The actual merge algorithm doesn't dominate the complexity.