[Python-ideas] Start argument for itertools.accumulate() [Was: Proposal: A Reduce-Map Comprehension and a "last" builtin]

[Raymond Hettinger]

> On Friday, April 6, 2018 at 8:14:30 AM UTC-7, Guido van Rossum wrote:
> On Fri, Apr 6, 2018 at 7:47 AM, Peter O'Connor <peter.ed... at gmail.com> wrote:
>>   So some more humble proposals would be:
>> 
>> 1) An initializer to itertools.accumulate
>> functools.reduce already has an initializer, I can't see any controversy to adding an initializer to itertools.accumulate
> 
> See if that's accepted in the bug tracker.

It did come-up once but was closed for a number reasons including lack of use cases.  However, Peter's signal processing example does sound interesting, so we could re-open the discussion.

For those who want to think through the pluses and minuses, I've put together a Q&A as food for thought (see below).  Everybody's design instincts are different -- I'm curious what you all think think about the proposal.


Raymond

---------------------------------------------

Q. Can it be done?
A. Yes, it wouldn't be hard.

        _sentinel = object()

        def accumulate(iterable, func=operator.add, start=_sentinel):
            it = iter(iterable)
            if start is _sentinel:
                try:
                    total = next(it)
                except StopIteration:
                    return
            else:
                total = start
            yield total
            for element in it:
                total = func(total, element)
                yield total

Q. Do other languages do it?
A. Numpy, no. R, no. APL, no. Mathematica, no. Haskell, yes.

    * http://docs.scipy.org/doc/numpy/reference/generated/numpy.ufunc.accumulate.html
    * https://stat.ethz.ch/R-manual/R-devel/library/base/html/cumsum.html
    * http://microapl.com/apl/apl_concepts_chapter5.html
      \+ 1 2 3 4 5
      1 3 6 10 15
    * https://reference.wolfram.com/language/ref/Accumulate.html
    * https://www.haskell.org/hoogle/?hoogle=mapAccumL


Q. How much work for a person to do it currently?
A. Almost zero effort to write a simple helper function:

   myaccum = lambda it, func, start: accumulate(chain([start], it), func)


Q. How common is the need?
A. Rare.


Q. Which would be better, a simple for-loop or a customized itertool?
A. The itertool is shorter but more opaque (especially with respect
   to the argument order for the function call):

        result = [start]
        for x in iterable:
             y = func(result[-1], x)
             result.append(y)

    versus:

        result = list(accumulate(iterable, func, start=start))


Q. How readable is the proposed code?
A. Look at the following code and ask yourself what it does:

        accumulate(range(4, 6), operator.mul, start=6)

   Now test your understanding:

        How many values are emitted?
        What is the first value emitted?
        Are the two sixes related?
        What is this code trying to accomplish?


Q. Are there potential surprises or oddities?
A. Is it readily apparent which of assertions will succeed?

        a1 = sum(range(10))
        a2 = sum(range(10), 0)
        assert a1 == a2

        a3 = functools.reduce(operator.add, range(10))
        a4 = functools.reduce(operator.add, range(10), 0)
        assert a3 == a4

        a4 = list(accumulate(range(10), operator.add))
        a5 = list(accumulate(range(10), operator.add, start=0))
        assert a5 == a6


Q. What did the Python 3.0 Whatsnew document have to say about reduce()?
A. "Removed reduce(). Use functools.reduce() if you really need it; however, 99 percent of the time an explicit for loop is more readable."


Q. What would this look like in real code?
A. We have almost no real-world examples, but here is one from a StackExchange post:

        def wsieve():       # wheel-sieve, by Will Ness.    ideone.com/mqO25A->0hIE89
            wh11 = [ 2,4,2,4,6,2,6,4,2,4,6,6, 2,6,4,2,6,4,6,8,4,2,4,2,
                     4,8,6,4,6,2,4,6,2,6,6,4, 2,4,6,2,6,4,2,4,2,10,2,10]
            cs = accumulate(cycle(wh11), start=11)
            yield( next( cs))       #   cf. ideone.com/WFv4f
            ps = wsieve()           #     codereview.stackexchange.com/q/92365/9064
            p = next(ps)            # 11
            psq = p*p               # 121
            D = dict( zip( accumulate(wh11, start=0), count(0)))   # start from
            sieve = {}
            for c in cs:
                if c in sieve:
                    wheel = sieve.pop(c)
                    for m in wheel:
                        if not m in sieve:
                            break
                    sieve[m] = wheel    # sieve[143] = wheel at 187
                elif c < psq:
                    yield c
                else:          # (c==psq)
                    # map (p*) (roll wh from p) = roll (wh*p) from (p*p)
                    x = [p*d for d in wh11]
                    i = D[ (p-11) % 210]
                    wheel = accumulate(cycle(x[i:] + x[:i]), start=psq)
                    p = next(ps) ; psq = p*p
                    next(wheel) ; m = next(wheel)
                    sieve[m] = wheel