Is reduce() foldl() or foldr()?
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
explains this a bit more. You might also like the Real World Haskell
More information about the Python-list