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

[Steven D'Aprano]

Calling all functional programming fans... is Python's built-in reduce()
a left-fold or a right-fold?

Wikipedia says it's a left-fold:

http://en.wikipedia.org/wiki/Fold_(higher-order_function)

but other people say it's a right-fold, e.g.:

"... there is a `foldr` in Haskell that just works like `reduce()`"
http://mail.python.org/pipermail/python-list/2007-November/638647.html


and

"Note that Python already has a variation of foldr, called reduce."
http://blog.sigfpe.com/2008/02/purely-functional-recursive-types-in.html


So which is correct? Or is it that different people have different
definitions of foldl() and foldr()?

 

[Tim Northover]

Calling all functional programming fans... is Python's built-in reduce()
a left-fold or a right-fold?

I get:

reduce(lambda a, b: a/b, [1.0, 2.0, 3.0])

0.16666666666666666

which looks like a left fold to me.

Tim.

 

[Peter Otten]

Calling all functional programming fans... is Python's built-in reduce()
a left-fold or a right-fold?

Wikipedia says it's a left-fold:

http://en.wikipedia.org/wiki/Fold_(higher-order_function)

Wikipedia is correct:

0.0083333333333333332

but other people say it's a right-fold, e.g.:

"... there is a `foldr` in Haskell that just works like `reduce()`"
http://mail.python.org/pipermail/python-list/2007-November/638647.html


and

"Note that Python already has a variation of foldr, called reduce."
http://blog.sigfpe.com/2008/02/purely-functional-recursive-types-in.html

The explicit foldr() function given in this blog agrees with Wikipedia's
definition:
.... if l == []:
.... return b
.... else:
.... return a(l[0], foldr(a, b, l[1:]))
....1.875

Peter

 

[Piet van Oostrum]

TN> I get:

reduce(lambda a, b: a/b, [1.0, 2.0, 3.0])

TN> 0.16666666666666666

TN> which looks like a left fold to me.

Yes, see the Haskell result:

Prelude> foldl (/) 1.0 [1.0, 2.0, 3.0]
0.16666666666666666
Prelude> foldr (/) 1.0 [1.0, 2.0, 3.0]
1.5

 

[Paul Rubin]

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