itertools comments [Was: Re: RELEASED: Python 2.3a2]

[Steven Taschuk]

Quoth Raymond Hettinger:
> "Alexander Schmolck"
  [...]
> > def xwindow(iter, n=2, s=1):
> >     r"""Move an `n`-item (default 2) windows `s` steps (default 1) at a
> time
> >     over `iter`.
> 
> I've needed this one only one time in twenty-five years of programming
> (for the markov algorithm).  Again, solid use cases are needed.

Schmolck's xgroup(it, n) is xwindow(it, n, n).

More seriously:

Go pairwise to compute a sequence's first differences (for its own
sake, or to, say, approximate a function's derivative or compute
its Newton series).

Generalizing, go k-wise to compute g(n) = f(n) - f(n-k).  (Some
stock analysts use this as an indicator; they call it "momentum",
I think.  They also use g(n) = f(n)/f(n-k).)

Go pairwise on a token stream to get one-token lookahead in a
parser.  (This one's my favourite.  But see below re "fading".)

Go 3-wise to smooth f(0), f(1), ... by replacing f(x) with the
average of f(x-1), f(x), and f(x+1).

Go 3-wise to implement Euler's sequence accelerator:
	t(n) = s(n+1) - (s(n+1) - s(n))**2/(s(n-1) - 2*s(n) + s(n+1))

Go 3-wise to compute linear automata in which the next state of a
cell depends on its neighbours' states.

These can be summarized by saying that going k-wise with step 1
implements a FIFO buffer k objects wide.  I don't think the
usefulness of such buffers is controversial, though it's certainly
open to question whether xwindow() would be the best way to
implement them.

All of the above (except for implementing xgroup() in terms of
xwindow()) use a step of 1.  I can only think of one case where a
step other than 1 or the window size would be useful: drawing a
Bezier spline on a polyline by first going pairwise to insert
midpoints, then going 3-wise with step 2 for the actual spline
computation.  But this is dubious as a use case, since it's pretty
much as easy, and probably clearer, to go 3-wise with step 1 on
the original data.  (More complicated splines than the one I have
in mind might do better.)

So perhaps the step argument is unnecessary.

Note also that these use cases differ in their desired behaviour
at the end of the sequence:
    - Most want the window to stop when its leading edge goes past the
      end of the underlying data.
    - The parser with lookahead wants the window to "fade out", stopping
      only when its *trailing* edge goes past the end of the underlying
      data.
    - A smoothing algorithm might want either of the above.
    - As Ratzleff pointed out, some use cases involving polygons want
      the leading edge to cycle back to the beginning of the sequence,
      stopping when the trailing edge reaches the end of the sequence.
The same point might be made for the beginning of the sequence: a
smoothing algorithm that wants fade-out might also want fade-in. 
When fading out (in), there's also the question of whether the
window ought to shrink (grow) or be padded out with, say, None.

One interpretation of this embarrassment of variation is that
xwindow() is an over-generalization.

-- 
Steven Taschuk                                7\ 7'Z {&~         .
staschuk at telusplanet.net                        Y r          --/hG-
                                            (__/ )_             1^1`