[Python-ideas] Add nullifier argument to functools.reduce?

[David Mertz]

So here's a version of my function that addresses Steven's points, and also
adds what I think is more useful behavior.  A couple points about my
short--but more than 3-line function.

* The notion of "attractor" here still follows the "we're all adults"
philosophy. That is, the 'stop_on' and 'end_if' arguments may very well not
actually specify genuine attractors, but simply "satisfaction" values.  In
the examples below these are completely unlike attractors, but this could
be useful also for something like numeric approximation algorithms where
some non-final reduction value is considered "good enough" anyway.

* To be more like the reduce() builtin, I raise TypeError on an empty
iterable with no 'start' value.

* Although it's not as cute in using itertools as much, but simply a
loop-with-test, I got rid of the "golf" artifact of potentially allocating
a large, useless list.

* Most interesting, I think, I separated a 'stop_on' collection of values
from a 'end_if' predicate.  This lets us generalize attractors, I believe.
 For a simple cyclic attractor, you could list several value in the
'stop_on' collection.  But even for a strange attractor (or simply a
complex one, or e.g. an attractor to a continuous set of values--think an
attractor to a circular, real-valued orbit), the predicate could, in
principle, capture the fact we reached the attractor.

#################################################
% cat reduce_with_attractor.py
#!/usr/bin/env python3
from itertools import *
from operator import add

def reduce_with_attractors(func, it, start=None, stop_on=(), end_if=None):
    it = iter(it)
    try:
        start = start if start!=None else next(it)
    except StopIteration:
        raise TypeError
    for x in accumulate(chain([start],it), func):
        if x in stop_on or (end_if and end_if(x)):
            break
    return x

print(reduce_with_attractors(add, range(100), stop_on=(2, 6, 17)))
print(reduce_with_attractors(add, range(100), stop_on=('foo','bar')))
print(reduce_with_attractors(add, range(100), end_if=lambda x: x>100))
#################################################


On Sat, Aug 23, 2014 at 7:19 PM, David Mertz <mertz at gnosis.cx> wrote:
>
> On Sat, Aug 23, 2014 at 6:53 PM, Steven D'Aprano <steve at pearwood.info>
wrote:
>>
>> On Sat, Aug 23, 2014 at 11:43:42AM -0700, David Mertz wrote:
>>
>> >   def reduce_with_attractor(func, it, start=None, end_if=None):
>> >       it = iter(it)
>> >       start = start if start!=None else it.__next__()
>> >       return list(takewhile(lambda x: x!=end_if,
>> >                             accumulate(chain([start],it), func)))[-1]
>>
>> A couple of points:
>>
>> - Don't use it.__next__(), use the built-in next(it).
>
>
> Yeah, good point.
>
>>
>> - To match the behaviour of reduce, you need to catch the StopIteration
>> and raise TypeError.
>
>
> Oh, OK.  Hadn't thought of that.
>
>>
>> - Your implementation eagerly generates a potentially enormous list of
>> intermediate results, which strikes me as somewhat unfortunate for a
>> functional tool like reduce. In other words, for some inputs, this is
>> going to perform like a dog, generating a HUGE list up front, then
>> throwing it all away except for the final value.
>
>
> I know.  I realized this flaw right away.  I was trying to be cute and
fit it in my promised 3 lines.  It would be better to put it in a loop to
realize the successive values, of course--but would take an extra line or
two.  Maybe there's a way to squeeze it in one line with itertools rather
than a regular loop though.
>
>>
>> > This gives you the accumulation up-to-but-not-including the attractor.
 I
>> > guess the OP wanted to return the attractor itself (although that seems
>> > slightly less useful to me).
>>
>> Not really. His use-case seems to be to short-cut a lot of unnecessary
>> calculations, e.g. suppose you write product() as reduce(operator.mul,
>> iterable). In the event that the product reaches zero, you can[1]
>> short-circuit the rest of the iterable and just return 0:
>>
>> product([1, 2, 3, 0] + [4]*1000000)
>>
>> ought to reduce 0, not 6, and the intent is for it to do so *quickly*,
>> ignoring the 4s at the end of the list.
>
>
> I guess that's true.  Although I can certainly imagine being interested
not only in the final attractor, but *that* it reached an attractor and
ended early.  Not sure how best to signal that.  Actually, now that I think
of it, it would be kinda nice to make the function
'reduce_with_attractorS()' instead, and allow specification of multiple
attractors.
>
> I welcome your improved version of the code :-).  Feel free to take a
whole 10 lines to do it right.
>
>>
>> [1] Actually you can't. 0 is no longer an attractor in the presence of
>> INF or NAN.
>
>
> I was sort of thinking of a "we're all adults here" attitude.  That is,
the "attractor" might not really be a genuine attractor, but we still trust
the caller to say it is.  I.e. my function would accept this call:
>
>     reduce_with_attractor(operator.mul, range(1,1e6), end_if=6))
>
> I'm making the claim that reaching '6' is a stopping point... which, well
it is.  No, it's not an actual attractor, but maybe a caller really does
want to stop iterating if it gets to that value anyway.  Hence 'end_if' is
actually an accurate name.
>
> --
> Keeping medicines from the bloodstreams of the sick; food
> from the bellies of the hungry; books from the hands of the
> uneducated; technology from the underdeveloped; and putting
> advocates of freedom in prisons.  Intellectual property is
> to the 21st century what the slave trade was to the 16th.




--
Keeping medicines from the bloodstreams of the sick; food
from the bellies of the hungry; books from the hands of the
uneducated; technology from the underdeveloped; and putting
advocates of freedom in prisons.  Intellectual property is
to the 21st century what the slave trade was to the 16th.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20140824/effb947d/attachment-0001.html>