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[0], foldr(a, b, l[1:])) ... >>> foldr(lambda x, y: x/y, 5, range(1, 5)) 1.875 Peter -- http://mail.python.org/mailman/listinfo/python-list
