Duplicatesが存在するかどうかを調べる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は、リストの長さである）です。