在SML中从列表中移除重复项

Question

我刚开始学习SML中的函数式编程，我想知道如何将以下两个函数合并为一个函数。函数isolate使用辅助函数'removes'来删除任意类型（'a）列表的重复项。

fun isolate [] = []
  | isolate (l as x::xs) = x::isolate(remove(x,xs))

fun remove (x,[]) = []
  | remove (x,l as y::ys) = if x = y then remove(x,ys) else y::remove(x,ys)

因为需要更好地理解SML中的构造，所以如何在isolate中包含函数remove呢？这可能看起来很琐碎，但我一直在思考并且无法想出解决方法。感谢你的帮助！

- macalaca

Answer 1

一个方法是只需在isolate中定义remove。

fun isolate [] = []
  | isolate (l as x::xs) =
      let fun remove (x,[]) = []
            | remove (x,l as y::ys) = if x = y
                                      then remove(x,ys)
                                      else y::remove(x,ys)
      in
        x::isolate(remove(x,xs))
      end

或者，为了将去重作为一个功能，可以使用库函数List.filter来执行与remove相同的操作。

fun isolate [] = []
  | isolate (x::xs) = x::isolate(List.filter (fn y => y <> x) xs)

- qaphla

---

这正是我一直在寻找的！谢谢你！ - macalaca

嘿@qaphla，当我编译你的代码时，我得到了一个运算符和操作数不一致的错误，我找不到错误所在。 - macalaca

没事了。当你在 let 的 'in' 部分调用 remove 方法时，你没有传递正确的参数。 - macalaca

Answer 2

我有一个想法：定义一个嵌套函数来检查列表中是否有重复元素：

fun set(nums:int list)=
  let fun duplicate(x:int, l:int list)=
    if null l
    then false
    else hd l=x orelse duplicate(x,tl l)
  in
      if null nums
      then []
      else
      let val s=set(tl nums)
      in if duplicate(hd nums,s)
         then s
         else hd nums::s
      end
  end

但它会提供一个列表，其中每个重复元素仅保留最后一个。

- Xinyi Li

Answer 3

我想提出以下解决方案来解决这个问题：

fun remove_duplicates(xs: int list) = 
    let
        fun check(xs: int list, item: int) =
            if null xs
            then false
            else if hd xs = item
            then true
            else check (tl xs, item)
        fun go_through_list(xs: int list) =
            if null xs
            then []
            else if check(tl xs, hd xs)
                 then go_through_list(tl xs)
                 else hd xs :: go_through_list(tl xs)
    in
        go_through_list(xs)
    end

这比@qaphla提出的解决方案需要更多的代码行。

- Igor

Answer 4

我的想法是先对列表进行排序，然后递归返回一个没有重复项的新列表：

fun remove_duplicates(l: int list) =
if null(l)
then []
else if null(tl l)
then l
else
    let
        fun compare(x: int, y: int) = x > y
        fun sort(l: int list) = ListMergeSort.sort(compare) l
        val l_sorted = sort(l)
    in
        if (hd l_sorted) = (hd (tl l_sorted))
        then remove_duplicates(tl l_sorted)
        else (hd l_sorted)::remove_duplicates(tl l_sorted)
    end

- Jonny Kong