2012-04-05 7 views
3

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 ...Finden Sie, ob Duplikate existieren 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 

danke!

+0

Sie wissen, dass SML/NJ Sets unterstützt? – Marcin

+0

meinst du benutzen falten oder finden? – MCR

+0

Nein, ich meine, dass Sie das Set verwenden können, um zu erkennen, ob Ihre Liste Duplikate enthält. – Marcin

Antwort

7

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.

+0

Ich habe das Problem gerade herausgefunden und genau das habe ich gemacht. Vielen Dank! – MCR

+0

Warum nicht eine Set-basierte Lösung, aus Interesse? – Marcin

+0

Manchmal denke ich, dass es eine Strafsteuer auf das Schreiben überflüssiger Bedingungen wie 'wenn ... dann wahr sonst ... 'geben sollte :) –