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

Scott David Daniels Scott.Daniels at Acm.Org
Sun Jun 7 14:53:28 CEST 2009


Steven D'Aprano wrote:
> Calling all functional programming fans... is Python's built-in reduce() 
> a left-fold or a right-fold? ...
> So which is correct? Or is it that different people have different 
> definitions of foldl() and foldr()?

Just test.  Floating point addition is not associative, so:

 >>> a = reduce(float.__add__, (4095 * 2. **n for n in range(100)))
 >>> b = reduce(float.__add__,(4095*2.**n for n in reversed(range(100))))
 >>> a - b
5.7646075230342349e+17

So, since a > b, it must be foldl (the first addition happens to the
first of the list).

Foldl is the eager-beaver's dream; foldr is the procrastinator's dream.

--Scott David Daniels
Scott.Daniels at Acm.Org



More information about the Python-list mailing list