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