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

Peter Otten __peter__ at web.de
Sun Jun 7 08:41:31 EDT 2009

```Steven D'Aprano wrote:

> 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:

>>> from __future__ import division
>>> (1/(2/(3/(4/5)))) # right
1.875
>>> ((((1/2)/3)/4)/5) # left
0.0083333333333333332
>>> reduce(lambda x, y: x/y, range(1, 6))
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:

>>> def foldr(a, b, l):
...     if l == []:
...             return b
...     else:
...             return a(l, foldr(a, b, l[1:]))
...
>>> foldr(lambda x, y: x/y, 5, range(1, 5))
1.875

Peter

```