[beagle3]

The equivalent python is:

    mss = lambda x: max(scan(lambda a,b: max(0,a+b),0,x))

assuming a definition "scan" (which is like "reduce", except it gives you all intermediate values), an example of which is:

    def scan(f,x0,x):
      r = [x0]
      for x1 in x:
        x0 = f(x0, x1)
        r.append(x0)
      return r

Note that the K is idiomatic whereas the python is (arguably) not. Of course, it could be worse; the advantage is that, much like math, the 9-char K version is pattern-matched by your eyes once you are familiar with it, whereas no other version presented here (or in almost any other language) can utilize that feature of your brain.

[cbsmith]

Oh goodness... don't do scan like that. Way easier (and more efficient) to use a generator:

    def scan(f, iterator, initial=0):
        yield initial
        yield from scan(f, iterator, f(initial, next(iterator)))

Even with python2, you could make a non-recursive version that'd be still shorter than your scan and faster. Alternatively, you could pair a coroutine with that reduce function....

But always be suspect of your code if you are iterating and appending to a list. Likely there is a much better way.

[beagle3]

First, it is not equivalent - next() cannot apply to range() output, for example - you will need to do some iter() games and watch out for iteration order side effects if your values are iterators vs. lists.

Second, it is ~10% faster, but that speed difference disappears completely if you eliminate the namespace lookup (that is, add e.g. "o = r.append" before the loop, and call o() instead of r.append() inside the loop). It potentially uses less memory - but not the way you did it (unless Python 3 gained TCO when I wasn't looking. Did it?) - your formulation does not load the call stack, but it does create len(iterator) generators that - until the innermost StopIteration - all need to live somewhere on the heap. recursive solutions without TCO are rarely good enough to replace iteration.

Even if you did it right, it's more efficient, but not significantly so timewise, and slightly easier to use iterators in general, yes. It is mostly space-efficient in general.

I think it is more idiomatic, though - and also Python2 compatible - to just replace references to 'r' with yield in my code, than using the recursive definition you gave above - which is more idiomatic in functional languages, but less in Python (and harder to debug in any language than the iterative version)

[cbsmith]

> First, it is not equivalent - next() cannot apply to range() output, for example - you will need to do some iter() games and watch out for iteration order side effects if your values are iterators vs. lists.

It uses generator/iteration semantics instead of list semantics. If you wrap the whole thing with a decorator like function that does:

    def scan_wrapper(f, x0, x):
        return list(scan(f, iter(x), x0)

You get the exact same semantics. For most cases (including the one you cited), the alternate semantics are actually better, more flexible, and avoid requiring a list to be built in the first place.

No problem with iteration order side effects either unless your f() somehow invalidates your iterable... and you still have some potential exposure there in your original implementation.

> Second, it is ~10% faster... > It potentially uses less memory...

Yeah, I think you are understating it to say the least. Not only are you using less memory, but you are saving having to rejuggle/resize the list all the time.

> (unless Python 3 gained TCO when I wasn't looking. Did it?)

I guess in a way it sort of did for the case of yield from: 'The iterator is run to exhaustion, during which time it yields and receives values directly to or from the caller of the generator containing the yield from expression (the "delegating generator").'

So, even without full on TCO (which is still possible... I'm not sure if they did it with yield from), you at least have direct pass through from the generator to the caller. Because of iterator semantics, that should mean that each of the generators gets created on an as needed basis and the previous generator should get destroyed right thereafter. It is possible though that it isn't quite doing it right, in which case I'll concede that I'm still allocating an N deep generator stack, but that is still likely to be more memory efficient because it isn't having to reallocate/resize/copy increasingly larger lists throughout the execution.

> recursive solutions without TCO are rarely good enough to replace iteration.

As I mentioned, you can do the recursive solution as well, and it has the advantage of working with old Python. Still simpler and still far more efficient (here it is with extra wrapping to keep the semantics the same):

    def scan(f, x0, x):
        def scan_helper():
            yield x0
            for x1 in x:
                x0 = f(x0, x)
                yield x0
        return list(scan_helper())

> It is mostly space-efficient in general.

You say that like when doing statistical analysis space-efficiency isn't a concern...

> I think it is more idiomatic, though - and also Python2 compatible - to just replace references to 'r' with yield in my code, than using the recursive definition you gave above - which is more idiomatic in functional languages, but less in Python (and harder to debug in any language than the iterative version)

I was actually mostly getting at using yield instead of list append. I was just trying to express it as tersely as possible, which unsurprisingly became Python 3 and a functional style mechanism.

While I agree that often there is a struggle to understand functional programming, I think in this case it is very idiomatic Python (particularly since they defined "yield from" specifically for cases like this), and the code is very simple, readable, and easier to verify for correctness.

[beagle3]

> Second, it is ~10% faster... > It potentially uses less memory...

> Yeah, I think you are understating it to say the least.

I actually measured it. It was 10% faster with a call to 'r.append', and within 0.1% with the append lookup hoisted out of the loop, on 1000 external iterations over 50,000 list items, minimum of 3, inconsistent which version was faster. my scanned function was def f(x,y): return max(0,x+y)

> You get the exact same semantics. For most cases (including the one you cited), the alternate semantics are actually better, more flexible, and avoid requiring a list to be built in the first place.

range() on Python3 is not a list, and the original works on it and yet you needed scan_wrapper(). I didn't try to fix it - I just tried to use your version and stumbled on the differences.

> but that is still likely to be more memory efficient because it isn't having to reallocate/resize/copy increasingly larger lists throughout the execution.

Instead you allocate a generator state each time. Surprisingly, it doesn't make a difference in practice (I've measured) - the python lists grow exponentially, so we have e.g. 20 allocations+copies instead of 1,000,000 generator state allocations. I would have expected the list to be faster - but there's no measurable difference.

> As I mentioned, you can do the recursive solution as well, and it has the advantage of working with old Python. Still simpler and still far more efficient (here it is with extra wrapping to keep the semantics the same):

Recursive takes about 10 times more memory. Seriously - no TCO means call stacks are not free. Instead of one object which I stored, you store about 10 in each call frame!

But yes, your latest version is the idiomatic preferred version style, IMO: it's also the most efficient. (And unlike the earlier python3 functional, it doesn't need a helper to fix the INPUT)

> You say that like when doing statistical analysis space-efficiency isn't a concern...

Of course it's a concern. I'm not saying it is not useful, I'm saying it is overrated, especially when compared to recursive solutions, which -- in python -- cost about 10 times more in stack space then you save in list space.

> I was just trying to express it as tersely as possible, which unsurprisingly became Python 3 and a functional style mechanism.

... and taking much more memory in the process, though believing that you are using less. Not blaming you - python overlooks these things. One of K's nice features is that the costs are mostly evident on a cursory look.

> I think in this case it is very idiomatic Python (particularly since they defined "yield from" specifically for cases like this), and the code is very simple, readable, and easier to verify for correctness.

The recursive functional version is speedwise comparable, and spacewise much less efficient than my (admittedly, stupid) version. It is easier to prove formally, but harder to debug with a debugger because of the generator stack (which is a call stack, even though it does not exhaust the C call stack like regular calls do).

Can we agree that your latest scan(), if we dropped the two lines that have "scan_helper" in them, is the most efficient, most idiomatic, most (py2 and py3) compatible and clearest?

[cbsmith]

> Can we agree that your latest scan(), if we dropped the two lines that have "scan_helper" in them, is the most efficient, most idiomatic, most (py2 and py3) compatible and clearest?

Yeah. Actually, I just generally liked your feedback here.