functional-programming - 查找是否存在重复项 SML NJ

Question

我想编写一个函数来搜索列表并查找该列表中是否有重复值。该函数应该返回一个 bool 值。这是我所在的位置，但这不起作用......

fun myFunc [] = true
myFunc(x::xs) = 
if(x=myFunc(xs)) then false
else myFunc(xs);

[1,2,2,3,4,5,6] should return true
[1,2,3,4,5,6,7] should return false
[1,2,3,4,5,6,1] should return true

谢谢!

Answer 1

正如 @Marcin 在评论中所说，一种简单有效的方法是使用 set 来检查重复。 SML/NJ 在Utility Library 中有许多可用的集合结构。 .

关于您的函数，您无法比较 x 和 myFunc xs 因为它们可能不具有相同的类型。空列表是没有重复项的列表(myFunc [] 应返回 false)。

这有效:

fun duplicated [] = false
  | duplicated (x::xs) = (List.exists (fn y => x = y) xs) orelse (duplicated xs)

但是，最坏情况的时间复杂度是O(n²)(n是列表的长度)，这相当效率低下。