This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Title: Add foldr and foldl to functional module
Type: Stage:
Components: Extension Modules Versions: Python 2.5
Status: closed Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: collinwinter, georg.brandl, jimjjewett
Priority: normal Keywords: patch

Created on 2006-01-19 18:50 by collinwinter, last changed 2022-04-11 14:56 by admin. This issue is now closed.

File name Uploaded Description Edit
functional.patch collinwinter, 2006-01-20 17:31 Add foldr and foldl to functional, against r42109
Messages (8)
msg49342 - (view) Author: Collin Winter (collinwinter) * (Python committer) Date: 2006-01-19 18:50
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.
msg49343 - (view) Author: Jim Jewett (jimjjewett) Date: 2006-01-20 15:32
Logged In: YES 

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

reduce(func, iter, initial)


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.

msg49344 - (view) Author: Collin Winter (collinwinter) * (Python committer) Date: 2006-01-20 15:44
Logged In: YES 

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])
>>> reduce(sub, [3, 2, 1], 0)

I'd be happy to update the patch to include references to
reduce() in relation to foldl.
msg49345 - (view) Author: Jim Jewett (jimjjewett) Date: 2006-01-20 16:12
Logged In: YES 

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)))
    foldl(minus, 0, [1,2,3]) <==> (((0 - 1) - 2) - 3)


    foldr(f, zero, [x1, x2, x3...xn]) 
    f(x1, f(x2, f(x3, ... f(xn, zero))))
    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.

msg49346 - (view) Author: Collin Winter (collinwinter) * (Python committer) Date: 2006-01-20 17:31
Logged In: YES 

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.
msg49347 - (view) Author: Georg Brandl (georg.brandl) * (Python committer) Date: 2006-01-20 17:43
Logged In: YES 

In any case, having those functions in functional, under
their "common" name, is a good thing IMHO.
msg49348 - (view) Author: Jim Jewett (jimjjewett) Date: 2006-01-20 17:46
Logged In: YES 

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.
msg49349 - (view) Author: Collin Winter (collinwinter) * (Python committer) Date: 2006-01-23 02:23
Logged In: YES 

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 #1412451.

Accordingly, I'm closing this current patch.
Date User Action Args
2022-04-11 14:56:15adminsetgithub: 42810
2006-01-19 18:50:19collinwintercreate