algorithm - SML (NJ) 中的滑动窗口算法实现

Question

我对 SML 相当陌生，我想知道滑动窗口算法是否可以在 SMLNJ 中实现。由于 SML 是一种函数式语言，与我之前编写的程序（Python、C、C++）相比，我发现它相当困难，作为一种练习方式，我一直在尝试将我的一些其他程序“翻译”成SMLNJ。我在尝试“翻译”一个用 C 语言编写的程序时遇到了我的第一个障碍，该程序使用了滑动窗口算法的变体。我希望我的 SML 代码不包含除基本 SMLNJ 包之外的任何其他签名（如果我的理解正确，它们会像库一样运行）。那么，在 SMLNJ 中是否有可能实现滑动窗口算法呢？可以通过列表完成吗？还是我想错了/错过了什么？我能找到的关于这个主题的材料相当有限，所以任何帮助将不胜感激。我不需要答案，只要朝着正确的方向前进。
谢谢

标签： algorithmsmlsmlnj

Answer 1

是的，您当然可以在 SML 中实现滑动窗口算法！例如，假设您想删除列表中的相邻重复项（例如，[1, 2, 3, 3, 2, 2]将变为[1, 2, 3, 2]）。以下是您可能会发现有用的两种技术：

显式递归

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] *)

在这里，我们对给定的列表进行递归，删除相邻的重复元素。

带尾拉链

解决滑动窗口问题的常用技术包括考虑一个元素以及以下元素。许多常见功能可以通过使用列表及其尾部的ListPair结构来恢复：

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)
    )