Accumulator

A Paul Graham classic, the accumulator function.

style
Author

A. Coady

Published

May 28, 2018

A Paul Graham classic, the accumulator function.

As an illustration of what I mean about the relative power of programming languages, consider the following problem. We want to write a function that generates accumulators– a function that takes a number n, and returns a function that takes another number i and returns n incremented by i.

(That’s incremented by, not plus. An accumulator has to accumulate.)

In Common Lisp this would be

(defun foo (n) (lambda (i) (incf n i)))

If you try to translate the Lisp/Perl/Smalltalk/Javascript code into Python you run into some limitations. Because Python doesn’t fully support lexical variables, you have to create a data structure to hold the value of n. And although Python does have a function data type, there is no literal representation for one (unless the body is only a single expression) so you need to create a named function to return. This is what you end up with:

def foo(n): s = [n] def bar(i): s[0] += i return s[0] return bar

Python users might legitimately ask why they can’t just write

def foo(n): return lambda i: return n += i

or even

def foo(n): lambda i: n += i

and my guess is that they probably will, one day. (But if they don’t want to wait for Python to evolve the rest of the way into Lisp, they could always just…)

There are other solutions, using function attributes or instances with a __call__ method, but none are substantially more elegant. The challenge predates Python 3, which introduced the nonlocal keyword, making this the presumably preferred solution:

def foo(n):
    def inc(x):
        nonlocal n
        n += x
        return n
    return inc

acc = foo(0)
acc(1)
acc(2)
3

There was also yet another alternative as of Python 2.6: using a generator as a coroutine.

def foo(n):
    while True:
        n += yield n

acc = foo(0)
next(acc)
acc.send(1)
acc.send(2)
3

To satisfy the challenge, that would need to be wrapped with a decorator. The triple partial expression below may seem a little obtuse, but it’s not as bad as it looks. Just unwind it one step at a time.

from functools import partial

@partial(partial, partial)
def coroutine(func, *args, **kwargs):
    gen = func(*args, **kwargs)
    next(gen)
    return gen.send

coroutine
functools.partial(<class 'functools.partial'>, <function coroutine at 0x10bf970e0>)
@coroutine
def foo(n):
    while True:
        n += yield n

foo
functools.partial(<function coroutine at 0x10bf970e0>, <function foo at 0x10bf7eb90>)
acc = foo(0)
acc
<function generator.send>
acc(1)
acc(2)
3

But what’s the most Pythonic solution? This author would argue… don’t. In my experience, I have never really needed global or nonlocal in production code. Typically it’s because the objects in question are mutable, so it’s not necessary to rebind a name in a different scope to a new object.

A typical tell of these kinds of code challenges are that they focus on the interface or implementation exclusively, never both in context. Python numbers are immutable, and have syntactic support for incrementing, so there’s nothing more readable about acc(...) instead of n += ....

Futhermore, the accumulator object is intended to be used repeatedly, such as in a loop. In a language with such strong iteration support as Python, it’s extremely likely that accumulation will occur in a iterative loop. Indeed, the real accumulator has since been added to the standard library.

import itertools

list(itertools.accumulate(range(10)))
[0, 1, 3, 6, 10, 15, 21, 28, 36, 45]