I am fairly new to SML and I was wondering if the sliding window algorithm can be implemented in SMLNJ. Since SML is a functional language , I find it fairly difficult compared to the languages I have written programs before (Python,C,C++), and as a way to practice I've been trying to "translate" some of my other programs to SMLNJ. I hit my first roadblock while trying to "translate" a program written in C, that uses a variation of the sliding window algorithm. I would like my SML code not to contain any other signatures (which operate like libraries if my understanding is correct) than the base SMLNJ package. So, is it even possible in SMLNJ to implement the sliding window algorithm? Can it be done through lists? Or am I thinking wrong/missing something? The material I could find on the subject was fairly limited, so any help would be appreciated. I don't need an answer, just a push to the right direction.
Thanks
Yes, you can certainly implement sliding window algorithms in SML!
For example, say you wanted to remove adjacent duplicates in a list (e.g., [1, 2, 3, 3, 2, 2] would turn into [1, 2, 3, 2]).
Here are two techniques you may find useful:
fun clean (x1 :: x2 :: xs) = if x1 = x2 then clean (x2 :: xs) else x1 :: clean (x2 :: xs)
| clean l = l (* if l is [] or [x] *)
Here, we recurse over the given list, removing adjacent duplicate elements.
A common technique to solving sliding window problems involves considering an element along with the following element.
Many of the common functionalities can be recovered via use of the ListPair structure on a list and its tail:
infix |>
fun x |> f = f x
fun clean [] = []
| clean (x :: xs) = x :: (
ListPair.zip (x :: xs, xs)
|> List.filter (fn (x1,x2) => x1 <> x2)
|> List.map (fn (_,x2) => x2)
)
(* or: *)
fun clean [] = []
| clean (x :: xs) = x :: (
ListPair.mapPartial
(fn (x1,x2) => if x1 = x2 then NONE else SOME x2)
(x :: xs, xs)
)