Is reduce() foldl() or foldr()?

Paul Rubin http
Sun Jun 7 19:25:41 CEST 2009


Steven D'Aprano <steve at REMOVE-THIS-cybersource.com.au> writes:
> Calling all functional programming fans... is Python's built-in reduce() 
> a left-fold or a right-fold?

It's a left fold. 

> but other people say it's a right-fold, e.g.:
> "... there is a `foldr` in Haskell that just works like `reduce()`"

That is correct in the sense that a coding situation where you'd use
reduce in Python would often lead you to use foldr (with its different
semantics) in Haskell.  This is because of Haskell's lazy evaluation.
Example: suppose you have a list of lists, like xss =
[[1,2],[3,4,5],[6,7]] and you want to concatenate them all.  (++) is
Haskell's list concatenation function, like Python uses + for list
concatenation.  So you could say

   ys = foldl (++) [] xss 

but if I have it right, that would have to traverse the entire input
list before it gives you any of the answer, which can be expensive for
a long list, or fail totally for an infinite list.  foldr on the other
hand can generate the result lazily, in sync with the way the caller
consumes the elements, like writing a generator in Haskell.  The
tutorial

   http://learnyouahaskell.com/higher-order-functions#folds

explains this a bit more.  You might also like the Real World Haskell
book:

   http://book.realworldhaskell.org



More information about the Python-list mailing list