Good with Computers

The Sixty North Blog

Improving Transducer Composition

In the previous article in this series we derived a Python implementation of transducers from first principles. We finished by showing how transducers can be composed together using regular function call application to give us a single composite reducer which can perform many operations with a single pass of reduce(). Specifically, we showed how to filter a range of integers using a primality testing predicate, and then mapped a squaring function over the primes, to give prime squares:

>>> reduce(filtering(
...            predicate=is_prime)(
...                reducer=mapping(
...                    transform=square)(
...                        reducer=appender)),
...        range(20),
...        [])
[4, 9, 25, 49, 121, 169, 289, 361]

Although this clearly works, composing transducers this way quickly becomes ungainly and the code certainly has a Lisp-ish flavour. Keeping track of the parentheses in Python, when we have function calls which return functions which we immediately call, is somewhat awkward. Most functional programming languages include a function called “compose” to help with composing functions; many imperative programming languages do not, including Python, so we’ll have to write one:

def compose(f, *fs):
    """Compose functions right to left.

    compose(f, g, h)(x) -> f(g(h(x)))

    Args:
        f, *fs: The head and rest of a sequence of callables. The
                rightmost function passed can accept any arguments and
                the returned function will have the same signature as
                this last provided function.  All preceding functions
                must be unary.

    Returns:
        The composition of the argument functions. The returned
        function will accept the same arguments as the rightmost
        passed in function.
    """
    rfs = list(chain([f], fs))
    rfs.reverse()

    def composed(*args, **kwargs):
        return reduce(
            lambda result, fn: fn(result),
            rfs[1:],
            rfs[0](*args, **kwargs))

    return composed

The signature of compose() forces us to accept at least one argument. The first part of the function reassembles the supplied arguments into a single list and reverses it to put it in first-to-last application order. We then define the inner composed() function which uses reduce() over the list of functions to apply each in turn, carrying the intermediate results forward. Any arguments to the composed() function are forwarded to the first function in the chain.

With compose() in our armoury, it becomes somewhat easier to specify multi-step composite reductions using transducers:

>>> reduce(compose(filtering(is_prime), mapping(square))(appender), range(20), [])
[4, 9, 25, 49, 121, 169, 289, 361]

This becomes even clearer if we put in some line breaks:

>>> reduce(compose(filtering(is_prime),
                   mapping(square))
               (appender),
           range(20),
           [])
[4, 9, 25, 49, 121, 169, 289, 361]

Now it’s hopefully easier to see that the call to compose() produces a new transducer to which we pass the appender reducer to get a composite reducer which performs filtering, mapping and appending in one step. It is this composite reducer we pass to reduce() along with the input range and the empty list seed value.

In the next article in our series on transducers, we’ll look at fixing some of the not-so-obvious shortcomings of the previous snippet and bringing the capabilities of our Python transducers more in line with those of the Clojure originals.

Stay in Touch

Our business hours are 08:00 to 16:00 CET/CEST.