reducein Python, we need to come to grips with what
reduceactually is. I find that the documentation for
reduceis rather poor, requiring a fair amount of thinking to determine just what you need to pass in as arguments. Instead, let's examine the origins of
reduceto better understand it.
Reduceoriginates outside of Python. It comes to Python through a contributed patch:
About 12 years ago, Python aquired lambda, reduce(), filter() and map(), courtesy of (I believe) a Lisp hacker who missed them and submitted working patches.That's not very helpful, so let's derive
The fate of reduce() in Python 3000
Guido van Rossum, 2005
reduceby abstracting from some examples. Instead of Lisp, I'll use Standard ML. SML has two key advantages over Lisp: the syntax is more approachable for the uninitiated, and its robust (Hindley-Milner) type system and pattern matching will make things a little clearer. I'll follow the definitions in SML rather than Python, so we'll refer to
reduce-like functions as folds, with argument order matching those in the Standard ML Basis Library.
Consider adding up a list of integers. In SML, that list is a linked list, so we'll have a typical recursive solution:
fun sum  = 0I've made use of pattern matching to define
| sum (h::t) = h + sum t
sumin terms of two cases, that of an empty list and of a non-empty list. The double colon is a cons operator, joining the head
tof the list.
map, a similar recursion scheme is used:
fun map f  = 
| map f (h::t) = (f h) :: (map f t)
Mapis written as a curried function, so different list processors can be defined by specifying just the function
map f, only giving the list later.1
Just about any function over a list uses the same recursion scheme. Let's extract that recursions scheme into a higher order function called
fun foldr f acc  = acc
| foldr f acc (h::t) = f(h, (foldr f acc t))
Foldrdeconstructs a list from right to left, starting with the tail and accumulating the values. As with
foldris a curried function.
The type of
foldrcan make it easier to understand:
('a * 'b -> 'b) -> 'b -> 'a list -> 'bThe first term, in the parentheses, describes the function
f; it takes a list element and an accumulator, returning an updated accumulator. The second argument to
foldris an initial value for the accumulator. Third is the list to process. Importantly, the types of the accumulator and the list elements can differ.
We can use
val sum = foldr Int.+ 0For
map, we'll introduce a helper function and use
fun map f lst = letTo get the helper function
fun maphead(x, acc) = (f x) :: acc
foldr maphead  lst
mapheadright, I just looked at the types needed for
foldrand wrote the obvious function to satisfy those types.
foldrallows elegant definition of our two example functions, there is a problem. As written,
foldrwalks through the entire list before starting to do any work. If the list is long, this can cause a stack overflow. We need a tail-recursive version, leading us naturally to
fun foldl f acc  = accIn contrast to
| foldl f acc (h::t) = foldl f (f(h, acc)) t
foldlprocesses the list from left to right, starting with the head. This definition of
foldlis tail recursive, so operates in constant space. It can also be used to define a tail recursive
foldrby reversing the list before passing it to
Foldlis substantially similar to
reducein Python. Next time, I'll translate the above definitions to Python, to make the connection transparent.
1 Having a curried
mapin SML makes for a big conceptual difference from the
mapin Python. It's quite reasonable to view
mapas transforming a function from acting on values to a function acting on lists of values, without
mapitself actually having anything to do with the list.