[Python-ideas] Reduce/fold and scan with generator expressions and comprehensions

[Steven D'Aprano]

On Tue, Oct 25, 2016 at 05:18:46AM -0200, Danilo J. S. Bellini wrote:

> > [...]. From what
> > I remember, the conclusion reached was that there are too
> > many degrees of freedom to be able to express reduction
> > operations in a comprehension-like way that's any clearer

Danilo, if you are going to quote somebody, especially when you copy and 
paste their words out of a completely different email from the one you 
are replying to, please tell us who you are quoting. It is not polite to 
quote somebody without attribution and out of context.


> I don't know if that's a conclusion from any other thread, but that's
> wrong. The only extra "freedom" required a way to access the previous
> output (or "accumulator", "memory", "state"... you can use the name you
> prefer, but they're all the same). How many parameters does itertools.scan
> have? And map/filter?

I do not know which email thread is being talked about here, but the 
conclusion is correct. In the most general case, you might want:

- the current value of some running total or result;
- the previous value of the running result;
- the value of the running result before that ("previous previous");
- and so on;
- more than one running calculation at the same time;
- the current sequence value (for x in [1, 2, 3]);
- the previous sequence value (previous value of x);
- the sequence value before that ("previous previous x");
- etc.

Recurrence relations are not all linear, and they don't always involve 
only the previous value. Fibonacci numbers need to track two previous 
running values:

F[n] = F[n-1] + F[n-2]

The Lagged Fibonacci generator is a pseudo-random number generator that 
uses a similar recurence, except instead of only needing to remember the 
previous two results, it remembers some arbitrary N previous results. 
E.g. we might say:

S[n] = S[n - 4] + S[n - 9]

and so we use the 4th-previous and 9th-previous result to generate the 
new one. Just having the current running result is not sufficient.


[...]
> Forget the word "reduce", some people here seem to have way too much taboo
> with that word, and I know there are people who would prefer a higher
> McCabe complexity just to avoid it. Perhaps there are people who prefer
> masochist rituals instead of using "reduce", who knows?

And perhaps there are people who think that using "reduce" and other 
functional idioms instead of good, clean, easy-to-understand, easy-to- 
debug imperative code is a "masochist ritual".


> but I
> wrote a lot about the scan use cases and no one here seem to have read what
> I wrote, and the only reason that matters seem to be a kind of social
> status, not really "reason". I probably wrote way more reasons for that
> proposal than annotations could ever have.

I read your use-cases. I went to the Github page and looked at the 
examples and the documentation. I didn't comment because it doesn't 
matter whether there is one use-case or a million use-cases, the 
fundamental question still applies: why do we need ANOTHER way of 
solving these problems when there are already so many? More use-cases 
doesn't answer that question. A million weak use-cases is still weak.

The obvious way to solve these use-cases is still an imperative 
for-loop. Python is not Haskell, it is not a functional programming 
language. It has some functional programming features, but it is not and 
never will be intended for arbitrarily complex code to be written in a 
pure functional style.

Comprehensions are intentionally kept simple. They are not a substitute 
for all loops, only the easy 80% or 90%. As confirmed by Nick Coghlan, 
comprehensions are absolutely and fundamentally intended as syntactic 
sugar for ONE and ONLY one pattern. For example:

    [expr for x in seq for y in seq2 if cond]

is sugar for:

    result = []
    for x in seq:
        for y in seq2:
            if cond:
                result.append(expr)


If you need to keep the previous sequence item, or a running total, or 
break out of the loop early, or use a while loop, you cannot use a 
comprehension.

So I'm afraid that completely rules out your idea of having a running 
total or result in a comprehension. That simply isn't compatible with 
the design of comprehensions as ruled by Guido and the core devs.

Could you change their mind? It's not impossible. If you have an 
compelling answer to the questions "why does this need to be part of 
comprehension syntax? why not use a for-loop, or itertools.accumulate?" 
then of course they will reconsider. But the barrier is very high. It is 
not a matter of more use-cases. We already have solutions to those 
use-cases. You have to explain why the existing solutions don't work.



-- 
Steve