如果发现存在重复SML NJ(Find if Duplicates Exist SML NJ)

我想编写一个函数，搜索列表中，如果有在此列表中任何重复值认定。 该函数返回一个布尔值。 下面是我在哪里，但是这是不工作...

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中的评论称，一个简单而有效的方法是使用一套用于检查重复。 SML / NJ有许多可用的组结构实用工具库 。

关于你的功能，你不能比较x和myFunc xs ，因为他们可能没有相同的类型。 而空列表是不重复的列表（ myFunc []应该返回false ）。

这工作：

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

然而，在最坏情况下的时间复杂度是O（n ^2）（ n是列表的长度），这是非常低效的。

文章来源: Find if Duplicates Exist SML NJ