查找重复项是否存在SML NJ

Question

我想编写一个单一的函数来搜索列表,并查找此列表中是否有任何重复值.该函数应返回一个布尔值.这是我在的地方,但这不起作用......

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是列表的长度),这是非常低效的.