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

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

Steven D'Aprano <steve at> 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

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

More information about the Python-list mailing list