Haskell: comportement surprenant de « groupBy »

Question

Je suis en train de comprendre le comportement de la fonction de la bibliothèque groupBy (de Data.List), qui prétend éléments du groupe d'une liste par une fonction « test d'égalité » adoptée en tant que premier argument. La signature de type suggère que le test d'égalité a juste besoin d'avoir le type

(a -> a -> Bool)

Cependant, quand je l'utilise (<) comme le "test d'égalité" dans GHCi 6.6, les résultats ne sont pas ce que je pense:

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

Au lieu de cela, je me attends séries de chiffres strictement de plus en plus, comme ceci:

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

Qu'est-ce que je suis absent?

Answer 1

Jetez un oeil à la GHC mise en œuvre de groupBy :

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

Maintenant, comparez ces deux sorties:

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]]

En bref, ce qui se passe est ceci: groupBy suppose que les tests de fonction donnée (le premier argument) pour l'égalité, et suppose donc que la fonction de comparaison est réflexif , transitive et symétrique (voir équivalence relation ). Le problème ici est que le moins que relation n'est pas réfléchi, ni symétrique.

---

Modifier : La mise en œuvre suivante suppose que transitivité:

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

Le fait que "<" est pas un test d'égalité.

Vous pourriez vous attendre un comportement parce que vous souhaitez mettre en œuvre différemment, mais ce n'est pas ce qu'il promet.

Un exemple des raisons pour lesquelles ce qu'il est une réponse en sortie raisonnable est si elle balaye à travers elle, faire

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

a maintenant 3 groupes d'éléments égaux. Donc, il vérifie si l'un d'entre eux sont en fait le même:

Comme il connaît tous les éléments de chaque groupe est égal, il peut juste regarder le premier élément de chaque, 1, 2 et 1.

1> 2? Oui! Ainsi, il fusionne les deux premiers groupes.

1> 1? Non! Ainsi, il quitte le dernier groupe soit.

Et maintenant, il est comparé tous les éléments pour l'égalité.

... seulement, vous n'avez pas réussi ce genre de fonction qu'il attend.

En bref, quand il veut un test d'égalité, donner il un test d'égalité.

Answer 3

Le problème est que la mise en œuvre de référence de groupBy dans le rapport Haskell compare les éléments contre le premier élément, de sorte que les groupes ne sont pas strictement croissante (ils ont juste à être tout plus grand que le premier élément). Ce que vous voulez est plutôt une version de groupBy qui teste sur adjacents , des éléments tels que la mise en œuvre

Je voudrais simplement souligner que la fonction exige également groupBy votre liste à trier avant d'être appliqué.

Par exemple:

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)]]

Ce comportement vient du fait que groupBy utilise la durée dans sa définition. Pour obtenir un comportement raisonnable qui ne repose pas sur nous avoir la liste sous-jacente dans un ordre particulier, nous pouvons définir une fonction:

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

Je voudrais simplement souligner que la fonction exige également groupBy votre liste à trier avant d'être appliqué.

Par exemple:

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)]]

Ce comportement vient du fait que groupBy utilise la durée dans sa définition. Pour obtenir un comportement raisonnable qui ne repose pas sur nous avoir la liste sous-jacente dans un ordre particulier, nous pouvons définir une fonction:

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