foldr function in Python

[Ant]

Hi all,

I've just been reading with interest this article:
http://caos.di.uminho.pt/~ulisses/blog/2007/11/20/foldr-the-magic-function/

It's a useful function that (with a more intuitive name) could prove a
compelling addition to the itertools module. In it's python form, it
would be something like this:

def reduce2 (fn, init, seq):
return reduce(fn, seq, init)

def foldr (function, initial):
return partial(reduce2, function, initial)

It's a bit different from the other itertools functions, in that
rather than producing an iterator, it produces a function which
reduces a iterator to a singe value.

The advantages I see over reduce are that (a) it provides incentive to
document the code and (b) it promotes reuse. For example:

value = reduce(lambda x, y: "%s%s%s" % (x, "," if x else "", y),
myList, "")

vs.

commaSeparate = foldr(lambda x, y: "%s%s%s" % (x, "," if x else "",
y), "")
commaSeparate(myList)

Of course the lambda function in this case could be a named function,
helping with both readability and reuse, but I think the latter is
conceptually easier to grasp when reading the code.

Discuss.

 

[oj]

Hi all,

I've just been reading with interest this article:http://caos.di.uminho.pt/~ulisses/blog/2007/11/20/foldr-the-magic-fun...

It's a useful function that (with a more intuitive name) could prove a
compelling addition to the itertools module. In it's python form, it
would be something like this:

def reduce2 (fn, init, seq):
return reduce(fn, seq, init)

def foldr (function, initial):
return partial(reduce2, function, initial)

It's a bit different from the other itertools functions, in that
rather than producing an iterator, it produces a function which
reduces a iterator to a singe value.

The advantages I see over reduce are that (a) it provides incentive to
document the code and (b) it promotes reuse. For example:

value = reduce(lambda x, y: "%s%s%s" % (x, "," if x else "", y),
myList, "")

vs.

commaSeparate = foldr(lambda x, y: "%s%s%s" % (x, "," if x else "",
y), "")
commaSeparate(myList)

Of course the lambda function in this case could be a named function,
helping with both readability and reuse, but I think the latter is
conceptually easier to grasp when reading the code.

Discuss.

It's basically just one line to implement:

foldr = lambda f, i: lambda s: reduce(f, s, i)

It's just reduce with currying, I'm not sure it adds that much to what
python already offers.

 

[Ant]

It's basically just one line to implement:

foldr = lambda f, i: lambda s: reduce(f, s, i)

It's just reduce with currying, I'm not sure it adds that much to what
python already offers.

Yes it's easy to implement. I did it in two steps because I think it's
easier to read. That's not the point I'm trying to make though. sum,
any and all are trivial to implement, yet they made it into the
builtin methods.

The point of those functions I believe to be to promote easier to
understand idioms. Without them people will continue to write ad hoc
reduce based versions (which are less readable and less efficient).
With sum, any and all in the standard library, it becomes easier to
write readable code, and so people will be more likely to do so.

The other benefit is to promote ways of thinking about code that you
may not have come across or thought about before. This is a common
situation when learning new languages - before learning python I would
never have thought to use map or reduce functions, and these are
trivially easy to implement.

So my point really is that foldr (perhaps renamed to make_reducer or
something) could create idioms that are more readable than using
reduce directly.

 

[Marc 'BlackJack' Rintsch]

So my point really is that foldr (perhaps renamed to make_reducer or
something) could create idioms that are more readable than using
reduce directly.

The name is definitely not so good because there is a `foldr` in Haskell
that just works like `reduce()`. For partial applying you can use
``lambda`` or `functools.partial()`, unfortunately not with keyword
arguments as needed to set the initial value because `reduce()` just
accepts positional arguments. So let's define `foldr()` in terms of
`reduce()`::

foldr = lambda func, initial, iterable: reduce(func, iterable, initial)

comma_separate = partial(foldr, insert_comma, '')

`insert_comma()` is left as an exercise for the reader.

I think that's better than a `make_reducer()`.

Of course it's a silly example because the "pythonic" way to define
`comma_separate()` is::

comma_separate = ','.join

Ciao,
Marc 'BlackJack' Rintsch

 

[Ant]

The name is definitely not so good because there is a `foldr` in Haskell

I haven't done any Haskell programming for maybe 6 years, so can't
remember a thing about it I assume then that in Haskell currying
is automatic - i.e. if you leave out arguments you get a curried
function back, is that correct?

foldr = lambda func, initial, iterable: reduce(func, iterable, initial)

comma_separate = partial(foldr, insert_comma, '')

`insert_comma()` is left as an exercise for the reader.

I think that's better than a `make_reducer()`.

Of course it's a silly example because the "pythonic" way to define
`comma_separate()` is::

comma_separate = ','.join

Well, yes of course. I have no use cases for this, hence the silly
example . It just occurred to me that it may be a more readable
solution than using reduce. But make_reducer is I agree a crap name,
and I can't think of a better one offhand. And I think that this would
only be valuable if an intuitive name could be found, otherwise people
reading the code would have the extra overhead of working out what the
function actually does...

 

[Steven D'Aprano]

Yes it's easy to implement. I did it in two steps because I think it's
easier to read. That's not the point I'm trying to make though. sum, any
and all are trivial to implement, yet they made it into the builtin
methods.

The point of those functions I believe to be to promote easier to
understand idioms. Without them people will continue to write ad hoc
reduce based versions (which are less readable and less efficient). With
sum, any and all in the standard library, it becomes easier to write
readable code, and so people will be more likely to do so.

Alas and alack, I believe that Guido has a distaste for all but the
simplest functional idioms, and an irrational belief that anything using
reduce() must be too complex to bear. reduce() is going away, not just
from the built-ins but (I believe) from the standard library as well.

The recommendation is that everybody wanting to reduce a sequence to a
single item should roll their own instead, using an accumulator and a for
loop instead. To my mind, getting rid of a standard functional tool like
reduce in favour of rolling your own is as irrational as getting rid of
for loops and telling people to roll their own from a while loop.

I hope to be proven wrong.

The other benefit is to promote ways of thinking about code that you may
not have come across or thought about before. This is a common situation
when learning new languages - before learning python I would never have
thought to use map or reduce functions, and these are trivially easy to
implement.

Not quite so trivial to implement as fast as the built-in reduce though.
A slow pure-Python reduce() would be a good way to disqualify reduce() as
a serious tool, and condemn it to be used only in toy examples.

So my point really is that foldr (perhaps renamed to make_reducer or
something) could create idioms that are more readable than using reduce
directly.

I believe that foldr() is a standard term in functional programming, and
no more difficult to learn than other programming terms like zip,
partition, map, iterator or curry.

 

[Steven D'Aprano]

Of course it's a silly example because the "pythonic" way to define
`comma_separate()` is::

comma_separate = ','.join

Except that join only works with strings, and reduce/foldr can work on
anything.

 

[Ant]

On Nov 23, 10:54 am, Steven D'Aprano <st...@REMOVE-THIS-
cybersource.com.au> wrote:
....

Alas and alack, I believe that Guido has a distaste for all but the
simplest functional idioms, and an irrational belief that anything using
reduce() must be too complex to bear. reduce() is going away, not just
from the built-ins but (I believe) from the standard library as well.

I thought that at the last count it was merely being moved out into
functools (or somewhere similar).

 

[Peter Otten]

On Nov 23, 10:54 am, Steven D'Aprano <st...@REMOVE-THIS-
cybersource.com.au> wrote:
...

I believe I've spotted an irrational belief in an irrational belief of the
BDFL here

I thought that at the last count it was merely being moved out into
functools (or somewhere similar).

reduce() is indeed in the functools -- added by Guido van Rossum himself.

Peter

 

[Steven D'Aprano]

reduce() is indeed in the functools -- added by Guido van Rossum
himself.

I am extremely glad to be wrong, you've cheered me up no end :-D

 

[greg]

The name is definitely not so good because there is a `foldr` in Haskell
that just works like `reduce()`.

Because currying is ubiquitous in Haskell, you can use the same
function in either a curried or non-curried fashion. But in
Python you need different functions for the different usage
styles.

My feeling is that Python shouldn't provide a bunch of
different versions of the same function that differ only in
the degree of currying. If you want a particular curried
combination, it's easy enough to create it as needed using
lambda, nested functions or partial().

 

[MonkeeSage]

My feeling is that Python shouldn't provide a bunch of
different versions of the same function that differ only in
the degree of currying. If you want a particular curried
combination, it's easy enough to create it as needed using
lambda, nested functions or partial().

I agree about noy having different functions with different levels of
currying.

What's interesting is that no-one has yet implemented a real foldr on
this thread -- all of the examples have been of foldl. The foldr is
right-associative. This doesn't matter for non-associative functions
like "+", but it does for associative functions like "-".

def foldl(f, l, i): # same as reduce()
if len(l) == 0:
return i
else:
return foldl(f, l[1:], f(i, l[0]))

def foldr(f, l, i):
l.reverse()
def _foldr(f, l, i):
if len(l) == 0:
return i
else:
return _foldr(f, l[1:], f(l[0], i))
return _foldr(f, l, i)

foldl(int.__sub__, [1,2,3,4], 0)
# -10

foldr(int.__sub__, [1,2,3,4], 0)
# -2

Regards,
Jordan

 

[MonkeeSage]

This doesn't matter for non-associative functions
like "+", but it does for associative functions like "-".

Err...that's backwards...should have been:

This doesn't matter for associative functions
like "+", but it does for non-associative functions like "-".