Saturday, September 8, 2012

Functional Programming


Today I was hacking on my TDT reading code when I came across the following ugly code:
if map(iscomplex, map(np.squeeze, map(np.array, args))):
    # ...
I thought to myself, "Hey why not throw some functional programming at this?", to get
if composemap(iscomplex, np.squeeze, np.array)(args):
    # ...
Definitely more readable if a little too terse.

What's great is that I can pass an arbitrary number of functions to compose map and it will run each function on all the arguments in args. Sweet.

How is it actually implemented?
def compose2(f, g):
    if not all(map(callable, (f, g))):
        raise TypeError('f and g must both be callable')
    return lambda *args, **kwargs: f(g(*args, **kwargs))
This little gem just returns a function that calls f and g with any number of arguments. Totally jacked from the Python functools module docs.
from functools import partial, reduce
from itertools import repeat

def composemap(*args):
    partial_map = map(partial, repeat(map, len(args)), args)
    return reduce(compose2, partial_map)
That's it! Now, to be sure there's a ton of stuff going on here and it took me a while to grok it, so let's break it down line by line.

The partial function takes a callable and optional positional and keyword arguments and returns another callable that has the given arguments already filled in. It's similar to currying, but a little different.

The first line of composemap results in
[partial(map, arg0), partial(map, arg1), ... partial(map, argN)].

This makes sense because what I want to do is actually run map, but with the functions I've provided as arguments first and whatever sequence i decided to map each of the functions I've provided over. However, I don't want to evaluate this right away so I create a list (actually a tuple) that contains all of the partial applications that I want to perform when I provide a sequence to map over.

OK whew! That was a lot to take in.

For the last line recall what partial does: it takes a callable with part of the sequence arguments that you want to provide and returns a callable with those arguments already set to go when you call the function with the final arguments (or more arguments).

Look at the reduce documentation for more details on reduce. If you're familiar with Haskell you can think of reduce as the Python version of foldl.

What I've done here is give reduce the list of partial functions that I want to eventually evaluate.

What the end result looks like is something like this

Given a function $h = f\circ g$ and an $n$-sequence of partial functions $\mathbf{p} = \left(p_1, p_2,\ldots,p_n\right)$ then the "reduce" function, in this case is given by
\begin{equation}
\textrm{reduce}\left(h, \mathbf{p}\right) = h\left(\ldots h\left(p_1, p_2\right), \ldots p_n\right)
\end{equation}

Recall that $h\left(f,g\right)$ returns a function. So running $h$ with $p_1,p_2$ as arguments gives $p_0\left(p_1\left(\cdot\right)\right)$. Pass that into $h$ with the third element of $\mathbf{p}$, $p_3$. Keep doing that until all of the arguments are eaten up.


















No comments:

Post a Comment