Re: [Haskell-cafe] Sliding windows for streaming

Unfortunately, much of that paper goes way over my head. On Sat, Jun 6, 2020, 8:07 PM Gershom B wrote:

On the specific question, the most general and natural thing to do, though not necessarily the most efficient, is to let users keep the length of items in each chunk as part of the semigroup.

More broadly, not a direct answer, but you may be interested in section 13 (on windowed algorithms) of http://gbaz.github.io/slides/buildable2014.pdf

The “parallelogram” algorithm there is quite general.

The paper also covers other interesting streaming algorithms worth having around such as (generalized) maximum segment sum, and parallel prefix scan.

- http://gbaz.github.io/slides/buildable2014.pdfg On Jun 6, 2020, 5:33 PM -0400, David Feuer , wrote:

I'm looking for a bit of help with a library design choice.

The streaming package currently offers a slidingWindow function converting a stream into a stream of fixed-size windows of that stream[1]:

slidingWindow :: Monad m => Int -- Window size -> Stream (Of a) m b -> Stream (Of (Seq a)) m b

This is based directly on a similar function in conduit. Using a rough translation into the world of lists, we have

slidingWindow 3 "abcdef" = ["abc","bcd","cde","def"]

The awkward case where the stream is shorter than the window is handled by potentially producing a short sequence at the end:

slidingWindow 3 "ab" = ["ab"] slidingWindow 3 "" = [""]

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[2].

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?

[1] https://hackage.haskell.org/package/streaming-0.2.3.0/docs/Streaming-Prelude...

[2] See the AnnotatedQueue in https://github.com/haskell-streaming/streaming/pull/99/files which basically modifies Okasaki's implicit queues using some of the basic ideas that appear in Hinze-Paterson 2–3 trees. _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries