A kind of sliding window-CodePudding

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]

CodePudding user response：

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