Liste Verständnis eindeutige Werte

Question

Ich frage mich, wie man die eindeutigen Werte aus einer Liste mit Haskell Liste Verständnis erhalten. Wenn ich also [2,4,5,4,4,6,2] eingeben würde, würde es zurückkehren [2,4,5,6].

Anfangs habe ich mit unique (y: ys) = [x | x < - (y: ys)] und ich weiß, dass ich eine andere Bedingung für x brauche, bin mir aber nicht sicher, wie ich dorthin komme.

Answer 1

Der Kommentar von @amalloy, dass Listen-Comprehensions auf eine "lokale" Perspektive beschränkt sind, ist der Schlüssel Einblick hier. Es gibt eine vernünftige Möglichkeit, nub als Listenverständnis zu schreiben, aber Sie müssen zuerst Ihre Perspektive ändern.

Eine oft nützliche Funktion, die leider aus der Bibliothek weggelassen wurde, ist die Funktion, die jedes Element einer Liste mit seinem Kontext schmückt.

picks :: [x] -> [([x], x, [x])] 
picks []  = [] 
picks (x : xs) = ([], x, xs) : [(x : bs, y, as) | (bs, y, as) <- picks xs] 

So

picks [1,2,3] = 
[([],1,[2,3]), ([1],2,[3]), ([1,2],3,[])] 

Jedes Element der Liste in der Mitte eines dreifachen gesetzt wird, mit den Elementen ‚vor‘ auf der linken und die Elemente ‚nach‘ auf der rechten Seite.

This answer of mine erklärt die tiefe Struktur, die picks in gewissem Sinne eine "Standard" -Operation macht, abgeleitet von der Struktur von Listen. Aber wir benötigen diese Hintergrundinformationen nicht, um sie zu implementieren.

Die picks Funktion gibt uns genau die kontextuellen Informationen, die wir nub als Listenverständnis schreiben müssen. Alles, was wir tun müssen, ist die Elemente auszuwählen, die nicht in ihren eigenen "Vorher-Listen" vorkommen.

myNub :: Eq x => [x] -> [x] 
myNub xs = [x | (bs, x, as) <- picks xs, not (elem x bs)] 

Ich mache keine Versprechungen in Bezug auf die Effizienz dieser Operation, aber ich mag die Klarheit, die sich aus der Kombination Listenkomprehensionen mit zusätzlichen räumlichen Kontext kommt.

Answer 2

Sie könnten es in einer (möglicherweise unnötig schlauen) Art und Weise mit Faulheit tun, indem Sie mit ein wenig Zirkelschluss beginnen: jedes Element der Eingabe sollte in der Ausgabe erscheinen, nur wenn es nicht in der Ausgabe erschienen ist.

Das heißt, für eine Eingabeliste wie [0, 0, 1] sollte die erste 0 hinzugefügt werden, aber die zweite 0 sollte nicht.

Klar, so etwas wie das wird nicht funktionieren:

unique xs = us 
    where us = [x | x <- xs, x `notElem` us] 

Weil es in einer Endlosschleife hängen bleiben wird, versuchen, Elemente der Ausgabe zu testen, die noch nicht erzeugt haben. Was Sie stattdessen tun können, ist die Argumentation zu ändern: jedes Element der Eingabe sollte in der Ausgabe erscheinen, nur wenn es nicht bereits erschien in der Ausgabe.

Sie können dies direkt implementieren, indem Sie berücksichtigen, was "bereits" bedeutet: Der aktuelle Wert darf nicht vor dem aktuellen Index bei Index aufgetreten sein.

unique xs = catMaybes us 
    where 
    us = 
     [ if Just x `elem` take i us -- If the element has appeared before here 
     then Nothing    -- then don’t include it again 
     else Just x     -- otherwise do include it. 
     | (i, x) <- zip [0..] xs  -- (Zip the elements with their indices.) 
     ] 

Also für die Eingabeliste xs = [0, 0, 1], würde dies generieren xs' = [Just 0, Nothing, Just 1], die durch catMaybes in [0, 1] abgeflacht werden würde.Das Testen mit QuickCheck bestätigt, dass dies nub entspricht, und hält an, weil wir nur die ersten take i Elemente von us bei jedem Schritt prüfen, wobei sichergestellt wird, dass keine noch nicht generierten Elemente untersucht werden.

Es ist bemerkenswert, dass, wie nub, dies ist O (n) in der Länge des Eingangs.