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

[Warren Weckesser]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20140823/a3d61636/attachment.html>