A kind of sliding window

Question

This function comes from some code to calculate convolutions of finite sequences.

window n k = [ drop (i-k) $ take i $ [1..n] | i <- [1..(n+k)-1] ]

*Main> window 4 6
[[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4],[1,2,3,4],[2,3,4],[3,4],[4]]

It's sliding window of length k over a sequence of length n, where k can be larger than n.

The code calls take and drop on the source list roughly n+k times, so it seems to have at least quadratic complexity.

Clearly, it can be written without a list comprehension:

window n k = map (\i -> (drop (i-k) . take i) [1..n]) [1..(n+k)-1]

Is there a better way to do this?

Edit: Full set of examples, as requested.

Prelude> window 4 4
[[1],[1,2],[1,2,3],[1,2,3,4],[2,3,4],[3,4],[4]]
Prelude> window 4 6
[[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4],[1,2,3,4],[2,3,4],[3,4],[4]]
Prelude> window 6 4
[[1],[1,2],[1,2,3],[1,2,3,4],[2,3,4,5],[3,4,5,6],[4,5,6],[5,6],[6]]

Computing the convolution of [1..4] and [1..5] works like this:

Prelude> let a = window 4 5
Prelude> let b = window 5 4
Prelude> map sum $ zipWith (zipWith (*)) a (map reverse b)
[1,4,10,20,30,34,31,20]

Define “better”. IMO it's rather dubious to have this function _at all_. Also, 1-based indexing, what the heck?? But I don't think there's an alternative implementation that's objectively better. — leftaroundabout, Sep 18 '21 at 16:19
`[]` isn't a very good type for a sliding window, as it can't share. How would you feel about `Data.Sequence.Seq` instead? — Carl, Sep 18 '21 at 16:23
@leftroundabout It's not 1-based indexing. Think of the function as a variation on `tail . inits`. — Theo H, Sep 18 '21 at 16:37
@n-1-8e9-wheres-my-share-m Would it clarify things for you if I said "`k` *may* be larger than `n`"? — Theo H, Sep 18 '21 at 17:58
since your function's arguments are numbers, and you generate the original sequence yourself over which to slide the window, you should directly generate each subsegment after calculating its starting and ending value. this way there won't be any `take`s and `drop`s. — Will Ness, Sep 19 '21 at 11:50
@WillNess Right, yes, that's a fair point, and answers my question. I actually want to use arbitrary lists. Something like altering the code to "deconstruct the input list one element at a time" (as you say here: https://stackoverflow.com/a/68145454/14768587) so that the lists in the result are built incrementally rather than recreated at each step. Maybe an unfold where the each resulting list is passed along? But such solutions seem to get more complex that they're worth. — Theo H, Sep 19 '21 at 22:03
I had the feeling. but you really should state all this relevant stuff upfront. with arbitrary sequences this is a completely different question. perhaps you should make a new post, linking to this as a reference. especially that now there's much less eyes on this question (practically none). as to "unfold" etc., when you start learning it's best (IMO) to just write recursive functions by hand, until you get the feel for it and it starts being extremely boring and extremely obvious. _then_ you switch to the higher-order functions, when you _recognize the pattern_ which you had to code by hand. — Will Ness, Sep 20 '21 at 07:36
Hmmm, that sounds a bit like a [recapitulation theory](https://en.wikipedia.org/wiki/Recapitulation_theory#Cognitive_development) of how people should learn to abstract away recursion. I don't particularly buy it, but thanks. — Theo H, Sep 20 '21 at 13:04
*altering the code to "deconstruct the input list one element at a time" so that the lists in the result are built incrementally rather than recreated at each step.* that's an interesting idea. --- re the repetitions, whether it takes 200 or 2, is entirely up to you. :) also, inventing some abstract syntax helps. I like the JS-like `[a, ...bs, ...cs, d]`, as one example, both to construct and to de-construct. at this level, folds and maps become uninteresting implementational detail too. (maybe)...... — Will Ness, Sep 20 '21 at 15:52
You never responded to @Carl's point about using sequences (or queues, really) instead of lists. — dfeuer, Sep 22 '21 at 00:10
@dfeuer I saw it. I guess the idea I had was to write a function to convolve two finite sequences, and do it without indexing and with as little explicit calculation involving lengths etc. as possible. I guess a possible discussion is whether `inits` and `tails` (and, later on, `zipWith`) on sequences are likely to be faster than on lists. [This comment](https://stackoverflow.com/a/29642956/14768587) suggests that they are, so perhaps I should look at converting @WillNess's approach to use `Data.Sequence.Seq`. — Theo H, Sep 22 '21 at 02:02
@TheoH, sliding a window is O(1) for a sequence (or any optimal queue), so that should be good. However, it depends a lot on what you're actually doing with the windows. For most purposes, you actually want to perform some calculation *instead of* actually forming windows. — dfeuer, Sep 22 '21 at 03:10

Will Ness · Accepted Answer · 2021-09-21T19:44:42.393

So you want to have a window of length k sliding over the given sequence (its length n is then not important).

It starts with just its last cell over the head of the sequence, then it moves along notch-by-notch until it covers the sequence's last element by its head cell.

This is then just map (take k) (tails sequence) with take k (inits sequence) in the front:

window :: Int -> [a] -> [[a]]
window k  =  (++) <$> take k . inits <*> map (take k) . tails

Observe:

> window 4 [1..6]
[[],[1],[1,2],[1,2,3],[1,2,3,4],[2,3,4,5],[3,4,5,6],[4,5,6],[5,6],[6],[]]

> window 6 [1..4]
[[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4],[2,3,4],[3,4],[4],[]]

You can take care of the []s by putting it through init . tail.

There's a discrepancy with your desired output in case k > n. If that's important an additional sequence of xs should be inserted between the two parts. Thus we get

-- NB: will diverge on infinite lists
window :: Int -> [a] -> [[a]]
window k xs
   = (init . tail) $ 
     take k (inits xs)
     ++ replicate (k-n-1) xs
     ++ map (take k) (tails xs)
   where 
   n = length xs

note: Measuring length is an anti-pattern; it is used here for prototyping purposes only. Because of it the function will get stuck on infinite lists. Instead, length should be fused in so the function will be productive, producing successive windows indefinitely right away.

So now we get

> window 4 [1..6]
[[1],[1,2],[1,2,3],[1,2,3,4],[2,3,4,5],[3,4,5,6],[4,5,6],[5,6],[6]]

> window 6 [1..4]
[[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4],[1,2,3,4],[2,3,4],[3,4],[4]]

tails is linear, and inits, normally quadratic, is capped by take k so in case k << n it'll be linear as well.

For completeness, here's a version which doesn't measure the length of the input list so it works for the infinite inputs as well:

window :: Int -> [a] -> [[a]]
window k xs | k > 0
   = a
     ++ replicate (k - length a) xs
     ++ (init . map (take k) . tails 
              . drop 1 $ xs)
   where
   a = take k . tail $ inits xs

Good observation that `replicate` can be given a negative argument, since it passes it straight to `take`. — Theo H, Sep 20 '21 at 19:03
@TheoH in case the argument `n` is negative, `replicate n` just produces `[]`. it _could_ be implemented as `take n . repeat`, but it could be implemented differently as well. — Will Ness, Sep 21 '21 at 06:41
OK, but to be clear, it's literally specified in Haskell 2010 as equivalent to `take n $ repeat`, so it inherits the behaviour of `take` by definition. — Theo H, Sep 21 '21 at 14:58
@TheoH yes, equivalent. as in "must behave exactly the same as ...". — Will Ness, Sep 21 '21 at 19:12

A kind of sliding window

1 Answers1