Haskell: удивительное поведение "groupBy"
Я пытаюсь выяснить поведение библиотечной функции 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]]
Что мне не хватает?
Ответы
Ответ 1
Посмотрите на реализацию ghc groupBy:
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:[email protected](x':_)) | cmp x x' = (x:y):ys
| otherwise = [x]:r
where [email protected](y:ys) = groupBy' cmp xs
Ответ 2
Тот факт, что "<" не является критерием равенства.
Вы можете ожидать некоторого поведения, потому что вы будете реализовывать его по-другому, но это не то, что он promises.
Примером того, почему он выводит, является разумный ответ, если он пробирается через него, делая
[1, 2, 3, 2, 4, 1, 5, 9] ->
[[1,2,3], [2,4], [1,5,9]]
Теперь имеет 3 группы равных элементов. Поэтому он проверяет, является ли кто-либо из них одним и тем же:
Поскольку он знает, что все элементы в каждой группе равны, он может просто посмотреть на первый элемент в каждом, 1, 2 и 1.
1 > 2? Да! Таким образом, он объединяет первые две группы.
1 > 1? Нет! Поэтому он оставляет последнюю группу.
И теперь он сравнивал все элементы для равенства.
..., вы не передали ему ту функцию, которую она ожидала.
Короче говоря, когда он хочет провести тест равенства, дайте ему тест равенства.
Ответ 3
Проблема заключается в том, что эталонная реализация groupBy в отчете Haskell сравнивает элементы с первым элементом, поэтому группы не сильно увеличиваются (они просто должны быть больше, чем первый элемент). Вместо этого вам нужна версия groupBy, которая тестирует соседние элементы, такие как реализация здесь.
