Finden Sie, ob Duplikate existieren SML NJ

Question

Ich möchte eine einzelne Funktion schreiben, die eine Liste durchsucht und findet, ob es Dubletten in dieser Liste gibt. Die Funktion sollte einen booleschen Wert zurückgeben. Hier ist, wo ich bin, aber das funktioniert nicht ...

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 

danke!

Answer 1

Wie @Marcin im Kommentar gesagt hat, ist eine einfache und effiziente Möglichkeit, Satz für die Überprüfung der Duplizierung zu verwenden. SML/NJ hat viele Satzstrukturen verfügbar in Utility Library.

In Bezug auf Ihre Funktion können Sie x und myFunc xs nicht vergleichen, da sie möglicherweise nicht den gleichen Typ haben. Und leere Liste ist eine Liste ohne Verdoppelung (myFunc [] sollte false zurückgeben).

Dies funktioniert:

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

jedoch die Worst-Case-Zeitkomplexität ist O (n) (n ist die Länge der Liste), die sehr ineffizient ist.