Haskell: überraschendes Verhalten von „groupBy“

Question

Ich versuche, das Verhalten der Bibliotheksfunktion groupBy (von Data.List), um herauszufinden, die von einer „Gleichheitstest“ -Funktion übergeben als erstes Argument für Gruppenelemente einer Liste vorgibt. Die Art Signatur legt nahe, dass der Gleichheitstest muss nur Typen hat

(a -> a -> Bool)

Allerdings, wenn ich (<) als die "Gleichheitstest" verwenden in GHCi 6.6, sind die Ergebnisse nicht, was ich erwarten:

ghci> groupBy (<) [1, 2, 3, 2, 4, 1, 5, 9]
[[1,2,3,2,4],[1,5,9]]

Stattdessen würde ich läuft streng immer mehr erwarten, wie folgt aus:

[[1,2,3],[2,4],[1,5,9]]

Was bin ich fehlt?

Answer 1

Haben Sie einen Blick auf die ghc Implementierung von groupBy :

groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _  []           =  []
groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs

Jetzt vergleichen diese zwei Ausgänge:

Prelude List> groupBy (<) [1, 2, 3, 2, 4, 1, 5, 9]
[[1,2,3,2,4],[1,5,9]]
Prelude List> groupBy (<) [8, 2, 3, 2, 4, 1, 5, 9]
[[8],[2,3],[2,4],[1,5,9]]

Kurz gesagt, was passiert, ist dies: groupBy geht davon aus, dass die gegebene Funktion (das erste Argument) Tests für die Gleichstellung und damit geht davon aus, dass die Vergleichsfunktion ist reflexive transitiv und symmetrisch (siehe ¨Aquivalenzrelation ). Das Problem hierbei ist, dass die weniger als Beziehung ist nicht reflexiv, noch symmetrisch ist.

---

Bearbeiten : Die folgende Implementierung nur davon ausgegangen, Transitivität:

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' _   []                        = []
groupBy' _   [x]                       = [[x]]
groupBy' cmp (x:xs@(x':_)) | cmp x x'  = (x:y):ys
                           | otherwise = [x]:r
  where r@(y:ys) = groupBy' cmp xs

Answer 2

Die Tatsache, dass "<" ist kein Gleichheitstest.

Sie können ein bestimmtes Verhalten erwarten, weil Sie es anders implementieren würde, aber das ist nicht das, was es verspricht.

Ein Beispiel dafür, warum, was es gibt eine vernünftige Antwort ist, wenn es durch sie fegt, macht

[1, 2, 3, 2, 4, 1, 5, 9] ->
[[1,2,3], [2,4], [1,5,9]]

hat nun drei Gruppen von gleichen Elementen. So prüft sie, ob einer von ihnen in der Tat ist die gleiche:

Da alle Elemente weiß in jeder Gruppe gleich ist, kann es auf dem ersten Elemente schaut nur in jeweils 1, 2 und 1.

1> 2? Ja! So verbindet er die ersten beiden Gruppen.

1> 1? Nein! So ist es die letzte Gruppe verlässt sein.

Und es ist jetzt alle Elemente auf Gleichheit verglichen.

... nur, du hast übergeben Sie es nicht die Art von Funktion erwartet.

Kurz gesagt, , wenn es einen Gleichheitstest will, geben es ein Gleichheitstest .

Answer 3

Das Problem ist, dass die Referenzimplementierung von groupBy im Haskell Bericht Elemente gegen das erste Element vergleicht, so dass die Gruppen nicht streng monoton wachsend (sie müssen nur alle größer als das erste Element sein). Was Sie wollen, stattdessen ist eine Version von groupBy, die auf testet neben -Elemente, wie die Umsetzung

Ich möchte nur darauf hinweisen, dass die groupBy Funktion Ihrer Liste auch, bevor sie angewendet sortiert werden muss.

Zum Beispiel:

equalityOp :: (a, b1) -> (a, b2) -> Bool
equalityOp x y = fst x == fst y

testData = [(1, 2), (1, 4), (2, 3)]

correctAnswer = groupBy equalityOp testData == [[(1, 2), (1, 4)], [(2, 3)]]

otherTestData = [(1, 2), (2, 3), (1, 4)]

incorrectAnswer = groupBy equalityOp otherTestData == [[(1, 2)], [(2, 3)], [(1, 4)]]

Dieses Verhalten kommt zustande, weil groupBy in seiner Definition mit Spanne. Um vernünftige Verhalten die sich nicht auf uns die zugrunde liegende Liste mit in einer bestimmten Reihenfolge können wir eine Funktion definieren:

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' eq []     = []
groupBy' eq (x:xs) = (x:similarResults) : (groupBy' eq differentResults)
    where similarResults   = filter (eq x) xs
          differentResults = filter (not . eq x) xs

Answer 4

Answer 5

Answer 6

Ich möchte nur darauf hinweisen, dass die groupBy Funktion Ihrer Liste auch, bevor sie angewendet sortiert werden muss.

Zum Beispiel:

equalityOp :: (a, b1) -> (a, b2) -> Bool
equalityOp x y = fst x == fst y

testData = [(1, 2), (1, 4), (2, 3)]

correctAnswer = groupBy equalityOp testData == [[(1, 2), (1, 4)], [(2, 3)]]

otherTestData = [(1, 2), (2, 3), (1, 4)]

incorrectAnswer = groupBy equalityOp otherTestData == [[(1, 2)], [(2, 3)], [(1, 4)]]

Dieses Verhalten kommt zustande, weil groupBy in seiner Definition mit Spanne. Um vernünftige Verhalten die sich nicht auf uns die zugrunde liegende Liste mit in einer bestimmten Reihenfolge können wir eine Funktion definieren:

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' eq []     = []
groupBy' eq (x:xs) = (x:similarResults) : (groupBy' eq differentResults)
    where similarResults   = filter (eq x) xs
          differentResults = filter (not . eq x) xs

Answer 7

Answer 8

Answer 9