<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>Hi David,<br>
</p>
<p>this problem reminds me a lot of a whole bunch of functions in
OpenCV, the image manipulation library. Applying a function on
every possible window of a specific size is one of the core tools
in image analysis, either as a moving 1D-function applied to every
row, or as a moving 2D-function on the whole image. So you might
find a lot of inspiration there. Note that the applied function is
called a "kernel" in that area.</p>
<p>I haven't looked at the library in some time, but here are a few
thoughts from what I remember:</p>
<p>First of all, thinking about the end of the stream is a good
idea. But what about the start of the stream? If the end of the
stream can have non-full windows, why shouldn't the first window
have exactly one element, the second have two, and so on until the
window size is reached? Or something completely different?<br>
</p>
<p>Now the most general idea for start and end of the stream would
be to let the user decide. In OpenCV, there are several standard
methods to handle image borders: cut all non-full windows (like
you do at the start of the stream right now), repeat the value at
the border to fill the gaps, take the min/max/average of the last
full window to fill the gaps etc. Why not let the user provide two
functions <tt>(Seq a → Seq a → Maybe (Seq a))</tt>. The first
argument is the first/last "full" sequence, the second one is the
non-full sequence to be filled, and the result is either a
sequence of up to window-size or <tt>Nothing</tt> to represent
that the result is to be cut. Let the user provide a record with
these functions as settings, provide several reasonable defaults,
and there you go.</p>
<p>So in essence, what I'm suggesting is something like</p>
<pre> data WindowingSettings a x m = WindowingSettings
{ windowStartHandler :: Seq a -> Seq a -> m (Maybe (Seq a))
, windowEndHandler :: Seq a -> Seq a -> m (Maybe (Seq a))
, windowFunction :: a -> m x
}
slidingWindowWith
:: (Monad m, Semigroup x)
=> WindowingSettings a x m
-> Int
-> Stream (Of a) m b
-> Stream (Of x) m b</pre>
<p>I would also suggest offering a version where <tt>windowFunction</tt>
is basically <tt>id</tt>. Why? Several of the most useful tools
want to apply their function to the whole window each time, for
example to calculate a weighted average or for edge/blob
detection. But they also need reasonable border handling. So their
implementation might look something like</p>
<pre> weightedAverage weigh size
= fmap (average . weigh)
. slidingWindowWith (bothEndsWith interpolateLinear) size
</pre>
<p>Of course a <tt>(Seq a)</tt> is a <tt>Semigroup</tt>, so if the
user wants a full <tt>(Seq a)</tt> they could always rebuild it
inside <tt>windowFunction</tt>. But why make that extra
difficult.</p>
<p>In fact <tt>id</tt> could be the default impelentation because <tt>WindowingSettings
should</tt> make a decent <tt>Functor</tt>. So a moving maximum
might look something like</p>
<pre class="moz-quote-pre" wrap=""> slidingWindowMax size = slidingWindowWith (Max <$> repeatBorders) size
</pre>
<p>Of course these cents still have some rough edges to iron out.
For example, I'm coming from the user side, so I have no idea
what's even possible on the inside. But I hope they are of use
anyway.<br>
</p>
<p>Cheers,<br>
MarLinn</p>
<div class="moz-cite-prefix">On 06/06/2020 23.32, David Feuer wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAMgWh9sJLu=ME=RZfpKJLcUYhxX+6XC0=QcqB+DKzhPq9H+Z0Q@mail.gmail.com">
<pre class="moz-quote-pre" wrap="">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] <a class="moz-txt-link-freetext" href="https://hackage.haskell.org/package/streaming-0.2.3.0/docs/Streaming-Prelude.html#v:slidingWindow">https://hackage.haskell.org/package/streaming-0.2.3.0/docs/Streaming-Prelude.html#v:slidingWindow</a>
[2] See the AnnotatedQueue in
<a class="moz-txt-link-freetext" href="https://github.com/haskell-streaming/streaming/pull/99/files">https://github.com/haskell-streaming/streaming/pull/99/files</a> which
basically modifies Okasaki's implicit queues using some of the basic
ideas that appear in Hinze-Paterson 2–3 trees.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
<a class="moz-txt-link-freetext" href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a>
Only members subscribed via the mailman list are allowed to post.</pre>
</blockquote>
</body>
</html>