Inkonsistente Implementierung von nubBy in Data.List?

Question

Ich wurde durch den Quellcode der nubBy Funktion in Data.List gehen:

nubBy     :: (a -> a -> Bool) -> [a] -> [a] 
#ifdef USE_REPORT_PRELUDE 
nubBy eq []    = [] 
nubBy eq (x:xs)   = x : nubBy eq (filter (\ y -> not (eq x y)) xs) 
#else 
nubBy eq l    = nubBy' l [] 
    where 
    nubBy' [] _   = [] 
    nubBy' (y:ys) xs 
     | elem_by eq y xs = nubBy' ys xs 
     | otherwise  = y : nubBy' ys (y:xs) 

mir Nun scheint es, dass die beiden oben genannten Versionen voneinander abweichen. Wenn ich die USE_REPORT_PRELUDE Version nehmen, bekomme ich

nubBy (>) [1..10] 
[1,2,3,4,5,6,7,8,9,10] 

während die anderen Implementierung Erträge

nubBy (>) [1..10] 
[1] 

Was ist der Grund?

Answer 1

Ich denke, dass nubBy die binäre boolesche Operation eine Äquivalenzbeziehung erfordert.

Dies ist in etwa im gleichen Geist von sortBy erfordert eine Vorbestellung Beziehung (reflexive & transitive). Wenn diese Anforderung ungültig ist, werden Quicksort und Mergesort zu nicht äquivalenten Algorithmen. Die Absicht des Haskell-Berichts besteht stattdessen darin, einer Implementierung zu erlauben, einen von ihnen (oder einen anderen korrekten Sortieralgorithmus) zu verwenden.

Ebenso, wenn der nubBy Vergleich zulässig ist eine Nicht-Äquivalenz, ist die Implementierung unnötigerweise gezwungen, genau die Referenz Prelude Algorithmus zu verwenden, die Verwendung einer effizienteren Alternative zu verhindern.

---

Um ehrlich zu sein, sind die genauen Anforderungen an die Betreiber, die an die "... Von" weitergegeben werden, nicht immer offensichtlich. Zum Beispiel scheint die Dokumentation von sortBy Korrektheit nur für totale Ordnungen zu garantieren, obwohl ich erwarte, dass die tatsächliche Implementierung auch für eine größere Klasse von Ordnungen funktioniert, vorausgesetzt, das Ergebnis wird bis zu der durch die Ordnung induzierten Äquivalenz interpretiert.

Die Dokumentation für nubBy besagt einfach, dass das erste Argument ein "benutzerdefiniertes Gleichheitsprädikat" ist. Es ist also nur für Gleichheit und nicht für beliebige Äquivalenzen garantiert.

aber mein Gefühl ist, dass, wenn ihre Umsetzung für die Gleichstellung funktioniert, ist es hat auch (up-to, natürlich gelesen wird das Ergebnis zur Verfügung gestellt) für Äquivalenzen zu arbeiten. Dies könnte tatsächlich beweisbar sein, indem die "free theorem", die mit dem nubBy-Typ assoziiert ist, ausgenutzt wird. Mein Mangel an Fachkenntnis mit parametricity verrät mich hier :)

Answer 2

Dort ist a GHC bug report darüber. Das Verhalten von nubBy stimmte ursprünglich mit der Prelude-Implementierung überein, wurde aber irgendwann als "Fix" zu another bug report geändert. Ich denke, die Jury ist noch immer nicht in der richtigen Richtung.

Sie können sehen, dass auf codepad.org Ihr Code [1,2,3,4,5,6,7,8,9,10] produziert; aber auf ideone.com produziert Ihr Code [1]. So verwendet man eindeutig eine ältere oder andere Implementierung von der anderen.