[Patches] [ python-Patches-1410119 ] Add foldr and foldl to functional module

Fri Jan 20 17:12:02 CET 2006

Patches item #1410119, was opened at 2006-01-19 13:50
You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1410119&group_id=5470

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Modules
Group: Python 2.5
Status: Open
Resolution: None
Priority: 5
Submitted By: Collin Winter (collinwinter)
Assigned to: Nobody/Anonymous (nobody)
Summary: Add foldr and foldl to functional module

Initial Comment:
This patch adds foldr and foldl functions to the
libfunctional.tex and test/test_functional to include
documentation and tests, respectively, for the new
code. The code has been checked for reference leaks
using --with-pydebug.

The patch is against svn revision 42097.

----------------------------------------------------------------------

Comment By: Jim Jewett (jimjjewett)
Date: 2006-01-20 11:12

Message:
Logged In: YES
user_id=764593

Guido thinks that reduce is too hard to understand, because
it is too broad.  It still won't be removed before python 3.
0.  Python three *might* appear as soon as five years from
now, and even then, reduce would probably still be kept in
the functional module.

(1)  Should the functional module also mention other
builtins, such as sum, filter, and even min and max?

(2)  Could you show the step-by-step for foldr?  I missed
while to figure out how it works even after *this* reminder.

At this point, my best guess is that

foldr(minus, 0, [1,2,3]) <==> (1 - (2 - (3 - 0)))
while
foldl(minus, 0, [1,2,3]) <==> (((0 - 1) - 2) - 3)

so

foldr(f, zero, [x1, x2, x3...xn])
<==>
f(x1, f(x2, f(x3, ... f(xn, zero))))
while
foldl(f, zero, [x1, x2, x3...xn])
<==>
f(f(f(f(f(zero, x1), x2), x3) ... ), xn)

but I'm still not *sure* I got it right.

----------------------------------------------------------------------

Comment By: Collin Winter (collinwinter)
Date: 2006-01-20 10:44

Message:
Logged In: YES
user_id=1344176

I was under the impression that reduce was going to be
removed at some point in the future?

In any case, while reduce() is indeed another name for
foldl, "reduce(func, reversed(iter), initial)" is not the
same thing as foldr().

"""
>>> def sub(a, b): return a - b
...
>>> foldr(sub, 0, [1, 2, 3])
2
>>> reduce(sub, [3, 2, 1], 0)
-6
"""

I'd be happy to update the patch to include references to
reduce() in relation to foldl.

----------------------------------------------------------------------

Comment By: Jim Jewett (jimjjewett)
Date: 2006-01-20 10:32

Message:
Logged In: YES
user_id=764593

What does this add over the (currently builtin) reduce?

reduce(func, iter, initial)

and

reduce(func, reversed(iter), initial)

Is it just that foldr and foldl are more modern names?
If so, it might be better to submit a documentation patch.
The functional module should mention reduce, and the reduce
documenation (library reference/Built-in Objects/Built-in
Functions) could be clarified.

Maybe even show how to create foldr and foldl as an example,
for reduce so that the terms can be picked up by indexers.

----------------------------------------------------------------------

You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1410119&group_id=5470