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

[Danilo J. S. Bellini]

2016-11-06 23:27 GMT-02:00 Wes Turner <wes.turner at gmail.com>:

> - So, IIUC, for recursive list comprehensions
>   - "prev" = x_(n-1)
>   - there is a need to define an initial value
>     - chain([1000], [...])
>   - sometimes, we actually need window function
>     - __[0] = x_(n-1)
>     - __[1] = x_(n-2)  # this
>     - __[-1] = x_(n-2)  # or this
>     - this can be accomplished with dequeue
>       - __= dequeue([1000], maxlen)
>     - for recursive list comprehensions, we'd want to bind e.g. __ to a
> dequeue
>
> [f(__[0], x) for x in y with __ = dequeue((1000,), 1)]
>

If I understood correctly, that's an alternative to get a general recursive
list comprehension with a syntax like:

[f(hist, x) for x in y with hist = deque([start_values], size)]

You're trying to solve the output lag/window problem using a circular queue
with random/indexed access to its values (a collections.deque instance).
You're using "with" instead of "from" to distinguish it from my first
proposal.

That's not a scan anymore, but something more general. Some information can
be removed from that syntax, for example the size can be defined to be the
starting iterable/memory/history data size, and the deque can be something
internal. Also, using the negative indices would be more explicit as
hist[-1] would be the previous iteration result, hist[-2] would be its
former result and so on. The syntax would be:

[func(hist, target) for target in iterable with hist = start_iterable]

i.e., this idea is about a new "with hist = start_iterable" at the end (or "
from" instead of "with"). The resulting list size would be
len(list(start_iterable))
+ len(list(iterable)). As a generator instead of a list, that can be
implemented as this "windowed scan" generator function:

>>> import collections
>>> def wscan(func, iterable, start_iterable):
...     pre_hist = []
...     for item in start_iterable:
...         yield item
...         pre_hist.append(item)
...     hist = collections.deque(pre_hist, len(pre_hist))
...     for target in iterable:
...         item = func(hist, target)
...         yield item
...         hist.append(item)

The Fibonacci example would be written as:

>>> list(wscan(lambda fibs, unused: fibs[-1] + fibs[-2], range(10), [0, 1]))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

With the "windowed scan" syntax proposal, it would become:

>>> [fibs[-1] + fibs[-2] for unused in range(10) with fibs = [0, 1]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

Or:

>>> [fibs[-1] + fibs[-2] for unused in range(10) from fibs = [0, 1]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

-- 
Danilo J. S. Bellini
---------------
"*It is not our business to set up prohibitions, but to arrive at
conventions.*" (R. Carnap)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20161114/758eeaed/attachment-0001.html>