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

[Tim Peters]

[Tim]
> Woo hoo!  Another coincidence.  I just happened to be playing with
> this problem today:
>
> You have a large list - xs - of N numbers.  It's necessary to compute slice sums
>
>     sum(xs[i:j])
>
> for a great many slices, 0 <= i <= j <= N.

Which brought to mind a different problem:  we have a list of numbers,
`xs`.  For each index position `i`, we want to know the largest sum
among all segments ending at xs[i], and the number of elements in a
maximal-sum slice ending at xs[i].

`accumulate()` is a natural way to approach this, for someone with a
functional language background.  You'll have to trust me on that ;-)

But there are some twists:

- The identity element for max() is minus infinity, which accumulate()
can';t know.

- We want to generate a sequence of 2-tuples, despite that xs is a
sequence of numbers.

- In this case, we do _not_ want to see the special initial value.

For example, given the input xs

[-10, 3, -1, 7, -9, -7, -9, 7, 4]

we want to generate

(-10, 1), (3, 1), (2, 2), (9, 3), (0, 4), (-7, 1), (-9, 1), (7, 1), (11, 2)

Note:  the largest sum across all non-empty slices is then
max(that_result)[0].  The code below could be easily changed to keep
track off that incrementally too, but this is already so different
from "plain old running sum" that I don't want more novelty than
necessary to make the points (a special initial value is needed, and
it's not necessarily insane to want to produce results of a different
type than the inputs).

The key part is the state updating function:

    def update(state, x):
        prevmax, count = state
        newsum = prevmax + x
        if newsum > x:
            return newsum, count + 1
        else:
            return x, 1

That's all there is to it!

Then, e.g.,

>>> from itertools import accumulate, chain
>>> import math
>>> xs = [-10, 3, -1, 7, -9, -7, -9, 7, 4]
>>> initial = (-math.inf, 1)
>>> result = accumulate(chain([initial], xs), update)
>>> next(result) # discard unwanted value
(-inf, 1)
>>> list(result)
[(-10, 1), (3, 1), (2, 2), (9, 3), (0, 4), (-7, 1), (-9, 1), (7, 1), (11, 2)]