This patch adds foldr and foldl functions to the
functional module. In addition, it updates
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.

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.

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.

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
the difference when reading your patch, and it took me a
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.

Logged In: YES
user_id=1344176

Ah, I had thought reduce was going away sooner than Python 3.0.

I've updated the patch to include an expansion of both foldl
and foldr (in the __doc__'s and the latex docs). Also
included are mentions of max, min, sum and filter, plus a
suggestion to go consult any one of the "Functional
Programming with Python" tutorials that a quick Google
search turns up.

Logged In: YES
user_id=1188172

In any case, having those functions in functional, under
their "common" name, is a good thing IMHO.

Logged In: YES
user_id=764593

Review: I recommend to apply this patch.

It includes test cases and documentation.

Cannot break backwards compatibility, as the entire module
is new in 2.5.

The added functions are reasonably standard for modern
functional programming, and they are in the functional
module, which would otherwise be fairly sparse.

Logged In: YES
user_id=1344176

I found a reference leak in my implementation of foldr.
While fixing it, I did a lot more work on the functional
module, which I've rolled into patch bpo-1412451.

Accordingly, I'm closing this current patch.