I recently merged a pull request that adds variations on sliding
window maxima and minima using what's apparently a "folklore"
algorithm. For example
slidingWindowMax 3 "abcbab" = "abcccb"
This is basically like
slidingWindowMax k = map maximum . slidingWindow k
except that an empty stream doesn't yield anything, to avoid undefined values.
The big advantage of these specialized functions is that rather than
having to take a maximum over a sequence of length `k` at each step,
they only do a constant (amortized) amount of work at each step. Nice!
But not very general. Suppose we want to take a moving average of some
sort, like an arithmetic mean, geometric mean, harmonic mean, or
median? That thought leads quite naturally to a data structure: a
queue holding elements of some arbitrary *semigroup* that efficiently
keeps track of the sum of all the elements in the queue.
While the choice of *data structure* is moderately obvious, the choice
of *sliding window function* is less so. The tricky bit is, again,
what happens when the stream is too short for the window. If you work
in the Sum semigroup and divide the results by the window size to get
a moving average, then a too-short stream will give a (single) result
that's completely wrong! Oof. What would be the most useful way to
deal with this? The streams in `streaming` give us the option of
producing a distinguished "return" value that comes after all the
yields. Would it make sense to *return* the incomplete sum, and the
number of elements that went into it, instead of *yielding* it into
the result stream? That seems flexible, but maybe a tad annoying. What
do y'all think?