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
-
2A sliding algorithm is just the repeated application of the same function to different neighborhoods (by translation). So I see no conceptual problem.user1196549– user11965492021-03-29 12:42:13 +00:00Commented Mar 29, 2021 at 12:42
-
1Translating non-functional code into functional code rarely leads down a good path. A sliding window maps pretty directly onto a list recursion.molbdnilo– molbdnilo2021-03-29 12:51:55 +00:00Commented Mar 29, 2021 at 12:51
Add a comment
|
1 Answer
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:
Explicit Recursion
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.
Zip-With-Tail
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)
)
