Jamie Neubert Pedersen (Jul 13 2024 at 07:16): Jamie Neubert Pedersen (Jul 13 2024 at 07:16):Hey there. I am using List.walk to walk a list. Is there an efficient way to do it but with a "sliding window" of e.g. 3 elements? I was trying to use List.walkWithIndex but I can only look backwards in the list because only the current results are sent as the state.
[1, 2, 3, 4, 5, 6]
|> List.walkWithIndex [] slidingAdd
slidingAdd = \results, element, index ->
if List.len results < 3 then
List.append results element
else
prevPrev = List.get results (index - 2)
prev = List.get results (index - 1)
List.append results (Num.add element (Num.add prev prevPrev))
This is an incorrect solution but just what I have so far and so you can see what I mean.
Jamie Neubert Pedersen (Jul 13 2024 at 07:20):Maybe it makes more sense to write it up like this for what I want the final thing to achieve.
Given a list [1, 2, 3, 4, 5, 6].
The program should traverse the list such that it can look at a sliding window like this:
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]
[4, 5, 6]
[5, 6]
[6]
Those arrays should be passed to a function that can then do what it wants with the input and append it to a results array.
Kiryl Dziamura (Jul 13 2024 at 07:32):Maybe List.sublist can help here?
Luke Boswell (Jul 13 2024 at 07:38):I made an example using recursion. :smiley:
module [
slidingWindow
]
slidingWindow : List a, List b, (List b, [Three a a a, Two a a, One a ] -> List b) -> List b
slidingWindow = \input, accum, fn ->
firstDropped = List.dropFirst input 1
when input is
[] -> accum
[a] -> slidingWindow firstDropped (fn accum (One a)) fn
[a,b] -> slidingWindow firstDropped (fn accum (Two a b)) fn
[a,b,c, ..] -> slidingWindow firstDropped (fn accum (Three a b c)) fn
exampleFn : List U64, [Three U64 U64 U64, Two U64 U64, One U64] -> List U64
exampleFn = \accum, window ->
when window is
One a -> List.append accum a
Two a b -> List.append accum (a + b)
Three a b c -> List.append accum (a + b + c)
expect
actual = slidingWindow [1,2,3] [] exampleFn
expected = [6, 5, 3]
actual == expected
Kiryl Dziamura said:
Maybe
List.sublistcan help here?
Thanks for the suggestion. The problem with List.sublist in the walking version is only having access to the state that has already been accumulated thus far. But maybe it could be used in conjunction with @Luke Boswell's version.
Luke Boswell said:
I made an example using recursion. :smiley:
module [ slidingWindow ] slidingWindow : List a, List b, (List b, [Three a a a, Two a a, One a ] -> List b) -> List b slidingWindow = \input, accum, fn -> firstDropped = List.dropFirst input 1 when input is [] -> accum [a] -> slidingWindow firstDropped (fn accum (One a)) fn [a,b] -> slidingWindow firstDropped (fn accum (Two a b)) fn [a,b,c, ..] -> slidingWindow firstDropped (fn accum (Three a b c)) fn exampleFn : List U64, [Three U64 U64 U64, Two U64 U64, One U64] -> List U64 exampleFn = \accum, window -> when window is One a -> List.append accum a Two a b -> List.append accum (a + b) Three a b c -> List.append accum (a + b + c) expect actual = slidingWindow [1,2,3] [] exampleFn expected = [6, 5, 3] actual == expected
Thank you for the recursive implementation. I'll look at it :smiley:. I had hoped to use a built-in iteration style like List.walk, but I might have to go with recursion. I am just weary of recursion because I am not proficient at making them tail-call optimized, thus blowing my stack :sweat_smile:
Luke Boswell (Jul 13 2024 at 07:46):We talked at some point about adding that as a feature to the language server I think, or maybe an editor extension that would give a little flag if the recursive function was TCO'd.
Jamie Neubert Pedersen (Jul 13 2024 at 07:47):That would be awesome :clap:
Richard Feldman (Jul 13 2024 at 11:21):also "walk with sliding window" seems like a plausible thing to add to the List module
Richard Feldman (Jul 13 2024 at 11:21):does anyone know of examples of functions like that in other languages?
Luke Boswell (Jul 13 2024 at 11:53):Yeah super common in digital signal processing algorithms.
https://www.mathworks.com/help/dsp/ug/sliding-window-method-and-exponential-weighting-method.html
https://en.m.wikipedia.org/wiki/Window_function
Anton (Jul 13 2024 at 11:58):sliding (does not take a function) is in the scala stdlib
Luke Boswell (Jul 13 2024 at 11:58):https://pkg.go.dev/gonum.org/v1/gonum/dsp/window
Luke Boswell (Jul 13 2024 at 12:00):https://doc.rust-lang.org/std/slice/struct.Windows.html
Jasper Woudenberg (Jul 13 2024 at 12:04):In ruby you have each_cons:
irb> [1,2,3,4].each_cons(2) { |x, y| puts "#{x} #{y}" }
1 2
2 3
3 4
=> [1, 2, 3, 4]
Super common for some math concepts too. It’s needed for convolutions of small size kernel for example https://en.wikipedia.org/wiki/Convolution. Bigger sizes usually implemented with Fourier transforms instead of sliding windows.
Brendan Hansknecht (Jul 13 2024 at 16:06):Yeah, definitely common operation in array languages. Though not used that often. Has niche but definite uses
Brendan Hansknecht (Jul 13 2024 at 16:07):And yeah, something with sublist is probably the way to go
Kiryl Dziamura (Jul 16 2024 at 09:15):The problem with
List.sublistin the walking version is only having access to the state that has already been accumulated thus far.
@Jamie Neubert Pedersen I meant smth like that:
slide = \list, windowSize ->
List.range { start: At 0, end: At ((List.len list) - windowSize) }
|> List.map \from ->
List.sublist list { start: from, len: windowSize }
expect
actual = slide [0, 1, 2] 2
expected = [[0, 1], [1, 2]]
actual == expected
Last updated: Jul 06 2025 at 12:14 UTC