W3R-2: Importing Reduce Into Python

Last time, we took a look at reduce in Standard ML, where it is known as a fold. Now, we'll translate those folds into Python. Let's keep calling them folds, reserving reduce for describing the existing Python function.

The main challenge in the translation process is that Python doesn't have the right data types—Python's lists are actually arrays, not (linked) lists. As a first step, introduce two classes Cons and Nil to define linked lists:

class Cons(object):

    def __init__(self, head, tail):
        self.head = head
        self.tail = tail

    def __iter__(self):
        lnkLst = self
        while True:
            if lnkLst.isNull():
                break
            yield lnkLst.head
            lnkLst = lnkLst.tail

    def __repr__(self):
        return "Cons(%s, %s)" % (repr(self.head), repr(self.tail))

    def isNull(self):
        return False

class Nil(object):

    def __repr__(self):
        return "Nil()"

    def __iter__(self):
        if False:
            yield

    def isNull(self):
        return True

With these classes, we can construct lists in a Lisp-like fashion:

Cons(0, Cons(1, Cons(2, Cons(3, Cons(4, Nil())))))

For convenience, we'll also introduce a function to convert a Python list into a linked list:

def fromList(lst):
    lnkLst = Nil()
    for x in lst[::-1]:
        lnkLst = Cons(x, lnkLst)
    return lnkLst

Using fromList(range(5)) is a lot easier than nesting Cons repeatedly, as shown above.

With linked lists available, it is easy to define a (left) fold:

def fold_recur(function, init, linkedList):
    if linkedList.isNull():
        result = init
    else:
        acc = function(init, linkedList.head)
        result = fold_recur(function, acc, linkedList.tail)
    return result

I'll note two important differences between the SML folds and fold_recur. First, the arguments to the function taken by fold_recur are reversed from those taken by its SML counterpart, in order to match Python's reduce. Second, and far more importantly, fold_recur is terribly broken because it is a tail recursive function, but only has Python's broken support for recursion to draw on. Trying to use fold_recur will cause stack overflows when the list is too long—that is, containing 1000 elements with the default recursion limit¹.

To rectify this problem, we need to transform fold_recur by hand into an imperative version. Fortunately, fold_recur is constructed in an iterative form, so the transformation is easy:

def fold_imper(function, init, linkedList):
    acc = init
    while not linkedList.isNull():
        acc = function(acc, linkedList.head)
        linkedList = linkedList.tail
    return acc

With the imperative definition, our fold will not cause a stack overflow.

Since we've defined linked lists to be iterable, we can still make our fold a bit more elegant:

def fold_ll_iter(function, init, linkedList):
    acc = init
    for x in linkedList:
        acc = function(acc, x)
    return acc

Although fold_ll_iter was obtained by iterating over a linked list, it will work with any iterable. Rewrite it to make that clearer:

def fold_iter(function, init, iterable):
    acc = init
    for x in iterable:
        acc = function(acc, x)
    return acc

Through this process, the deconstruction of a data structure has been shifted from SML fold functions to Python iterators. This is unsurprising: in Python, it is quite standard to use iterators to deconstruct data structures. It is not completely equivalent, but covers many cases.

The iterator approach suggests another modification of fold, which is normally called scan:

def scan(function, init, iterable):
    acc = init
    yield acc
    for x in iterable:
        acc = function(acc, x)
        yield acc

Our scan function processes the list in the same sequence, yielding values accumulated at each step along the way. Using scan, we define one last version of fold:

def fold(function, init, iterable):
    for x in scan(function, init, iterable): pass
    return x

We can use scan and fold to define many useful functions in a simple manner. For example:

import operator
def sum(numbers): return fold(operator.add, 0, numbers)
def cumsum(numbers): return scan(operator.add, 0, numbers)
def product(numbers): return fold(operator.mul, 1, numbers)
def cumproduct(numbers): return scan(operator.mul, 1, numbers)

I think these functions illustrate rather well the difference between fold and scan. In sum, we use fold to total up the numbers in a list, while in cumsum we use scan to generate the partial sums as we proceed through the list. The product and cumproduct functions are similar.

More complex functions are possible as well. Consider finding the three smallest items in a list. This can be done in linear time by iterating through the list and keeping track of the three smallest as we proceed. But that's exactly what fold is for! The accumulator is a collection of the three smallest items, and we just need a function to update that. Putting that together:

def min3(lst):
    def comp(acc, x):
        a,b,c = acc
        if x < a:
            result = x,a,b
        elif x < b:
            result = a,x,b
        elif x < c:
            result = a,b,x
        else:
            result = acc
        return result
    init = sorted(lst[:3])
    return fold(comp, init, lst[3:])

For simplicity, I've assumed that min3 takes a list, but it could easily be modified to work with any iterable.

I've presented a lot of program code in this post, transforming a direct translation of the SML folds into function that are defined in a more natural way for Python. Next time, I'll digress briefly to present an alternative structure that has some practical advantages over what's been shown here, then return to examining why reduce doesn't see much use in Python.

---

¹ In practice, this might as well read that the limit is 1000 elements, end of story. The limit can be increased with sys.setrecursionlimit, but "a too-high limit can lead to a crash."