Хаскелл:удивительное поведение «groupBy»

Question

Я пытаюсь выяснить поведение библиотечной функции groupBy (из Data.List), которая предназначена для группировки элементов списка с помощью функции «проверки равенства», передаваемой в качестве первого аргумента.Сигнатура типа предполагает, что тест на равенство просто должен иметь тип

(a -> a -> Bool)

Однако когда я использую (<) в качестве «проверки равенства» в GHCi 6.6, результаты не такие, как я ожидал:

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

Вместо этого я бы ожидал серии строго возрастающих чисел, например:

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

Что мне не хватает?

Answer 1

Взгляните на ГК реализация группа по:

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

Теперь сравните эти два результата:

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

Вкратце, происходит следующее: groupBy предполагает, что данная функция (первый аргумент) проверяет равенство, и, таким образом, предполагает, что функция сравнения рефлексивный, переходный и симметричный (видеть отношение эквивалентности).Проблема здесь в том, что меньше, чем Отношение не является ни рефлексивным, ни симметричным.

---

Редактировать:Следующая реализация предполагает только транзитивность:

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

Тот факт, что «<» не является проверкой равенства.

Вы можете ожидать некоторого поведения, потому что реализуете его по-другому, но это не то, что оно обещает.

Примером того, почему то, что он выводит, является разумным ответом, является то, что он просматривает его, выполняя

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

Теперь имеет 3 группы одинаковых элементов.Поэтому он проверяет, действительно ли какие-либо из них одинаковы:

Поскольку он знает, что все элементы в каждой группе равны, он может просто просмотреть первый элемент в каждой: 1, 2 и 1.

1 > 2?Да!Таким образом, он объединяет первые две группы.

1 > 1?Нет!Таким образом, остается последняя группа.

И теперь он сравнивает все элементы на равенство.

... только вы не передали ему ту функцию, которую он ожидал.

Суммируя, когда ему нужен тест на равенство, дайте ему тест на равенство.

Answer 3

Проблема в том, что эталонная реализация groupBy в отчете Haskell сравнивает элементы с первым элементом, поэтому группы не увеличиваются строго (все они должны быть больше первого элемента).Вместо этого вам нужна версия groupBy который тестирует на соседний элементы, такие как реализация здесь.

Answer 4

Я просто хотел бы отметить, что функция groupBy также требует, чтобы ваш список был отсортирован перед применением.

Например:

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

Такое поведение возникает из-за того, что groupBy использует в своем определении диапазон.Чтобы получить разумное поведение, которое не зависит от наличия базового списка в каком-либо определенном порядке, мы можем определить функцию:

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