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

[Warren Weckesser]

On Sat, Aug 23, 2014 at 1:25 PM, David Mertz <mertz at gnosis.cx> wrote:

> This "nullifier" is mathematically called an "absorbing element", but
> saying an "attractor" might be a little more general.  I.e. think of a
> local optimization problem, where multiple local min/max points might
> occur.  If you reach one, further iteration won't budge from that point,
> even if it's not the "global absorbing element."
>
>

I took the name "nullifier" from
    http://www.mayhematics.com/m/m2_operations.htm
but a less "mathy" name would probably be better.  For consistency, I'll
stick with it, but you can think of it as a placeholder for a better name
to be determined later.



> However, any such argument--including the much more useful
> sentinel/'stop_on' idea--significantly changes the semantics of reduce.  In
> particular, as is reduce() always consumes its iterator.  Under these
> changes, it may or may not consume the iterator, depending on what elements
> occur.
>
>

I don't agree that this change "significantly changes the semantics of
reduce".  The nullifier is optional.  The short-circuit can only occur when
the caller has specified a nullifier, so anyone using it will be aware that
the iterable might not be consumed.  Indeed, that's the *point* of using it.

Assuming the nullifier given is truly a nullifier of the function, the
result of the call to reduce should be the same (other than the amount by
which the iterable  has been consumed) whether or not the nullifier is
given.  (That was also Hernan's point.)



> Given that one can easily write one's own three line wrapper
> 'reduce_with_attractor()' for this special semantics which hasn't been
> given a use case,
>


My interest in the enhancement is purely performance.  Here's an example
(call it a use case, if you like) that is obviously cooked up to maximize
the benefit of short-circuiting.  In the following ipython session,
`reduce` is the builtin function  (I'm using python 2.7 here), and
`myreduce.reduce` is the python implementation with the nullifier argument:

    In [40]: a = range(100)

    In [41]: %timeit reduce(lambda x, y: x*y, a)
    100000 loops, best of 3: 8.89 µs per loop

    In [42]: %timeit myreduce.reduce(lambda x, y: x*y, a, nullifier=0)
    1000000 loops, best of 3: 455 ns per loop



> I can't see a point of including the argument in the stdlib.
>
> -1 on proposal.
>
>
>

I think the main objection (here and in other comments) is that the benefit
(performance gain in certain cases) does not outweigh the cost (a more
complicated API for reduce(), and more code and documentation to maintain
in the standard library).  That's a compelling argument!  I think the
enhancement would be useful, but I understand that it might not be useful
enough to accept such a change, especially since the cost of *not* having
it in the library to a user who wants such a feature is pretty low (i.e. it
is easy to "roll your own").

Warren



>
> On Sat, Aug 23, 2014 at 8:30 AM, Warren Weckesser <
> warren.weckesser at gmail.com> wrote:
>
>> I'd like to add an additional optional argument to functools.reduce.
>> The argument is the "nullifier" of the reducing operation.  It is a value
>> such that function(nullifier, anything) returns nullifier.  For example,
>> if
>> function(x, y) computes x*y, the nullifier is 0.  If function(x, y) is
>> the intersection of the sets x and y, the nullifier is the empty set.
>>
>> The argument would allow reduce to "short circuit" its calculation.   When
>> reduce encounters the nullifier, it can return immediately.  This can
>> provide
>> a significant improvement in performance in some cases.
>>
>> The change is simple.  Here, for example, is  the "rough equivalent" for
>> functools.reduce from the docs:
>>
>>     def reduce(function, iterable, initializer=None):
>>         it = iter(iterable)
>>         if initializer is None:
>>             try:
>>                 initializer = next(it)
>>             except StopIteration:
>>                 raise TypeError('reduce() of empty sequence with no
>> initial value')
>>         accum_value = initializer
>>         for x in it:
>>             accum_value = function(accum_value, x)
>>         return accum_value
>>
>> Here's how it looks with the optional nullifier argument; the only
>> change is the new argument and an 'if' statement in the 'for' loop.
>>
>>     def reduce(function, iterable, initializer=None, nullifier=None):
>>         it = iter(iterable)
>>         if initializer is None:
>>             try:
>>                 initializer = next(it)
>>             except StopIteration:
>>                 raise TypeError('reduce() of empty sequence with no
>> initial value')
>>         accum_value = initializer
>>         for x in it:
>>             if nullifier is not None and accum_value == nullifier:
>>                 break
>>             accum_value = function(accum_value, x)
>>         return accum_value
>>
>> (It might be better to use a distinct singleton for the default
>> value of nullifier, to allow None to be a valid nullifier.)
>>
>> The actual implementation is in the extension module _functoolsmodule.c.
>> It looks like the changes to the C code should be straightforward.
>>
>>
>> Warren
>>
>>
>> _______________________________________________
>> Python-ideas mailing list
>> Python-ideas at python.org
>> https://mail.python.org/mailman/listinfo/python-ideas
>> Code of Conduct: http://python.org/psf/codeofconduct/
>>
>
>
>
> --
> 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/df3e336c/attachment-0001.html>