У меня есть две функции Haskell, оба из которых кажутся мне очень похожими. Но первый ОТКАЗЫВАЕТСЯ против бесконечных списков, а второй - УНИЧТОЖЕТ против бесконечных списков. Я уже много часов пытаюсь понять, почему это так, но безрезультатно.
Оба фрагмента являются повторной реализацией функции "слов" в Prelude. Оба отлично работают с конечными списками.
Здесь версия, которая НЕ обрабатывает бесконечные списки:
myWords_FailsOnInfiniteList :: String -> [String]
myWords_FailsOnInfiniteList string = foldr step [] (dropWhile charIsSpace string)
where
step space ([]:xs) | charIsSpace space = []:xs
step space (x:xs) | charIsSpace space = []:x:xs
step space [] | charIsSpace space = []
step char (x:xs) = (char : x) : xs
step char [] = [[char]]
Здесь версия, которая обрабатывает бесконечные списки:
myWords_anotherReader :: String -> [String]
myWords_anotherReader xs = foldr step [""] xs
where
step x result | not . charIsSpace $ x = [x:(head result)]++tail result
| otherwise = []:result
Примечание: "charIsSpace" является просто переименованием Char.isSpace.
Следующий сеанс интерпретатора показывает, что первый из них терпит неудачу в отношении бесконечного списка, а второй - успешно.
*Main> take 5 (myWords_FailsOnInfiniteList (cycle "why "))
*** Exception: stack overflow
*Main> take 5 (myWords_anotherReader (cycle "why "))
["why","why","why","why","why"]
РЕДАКТОР: Благодаря ответам ниже, я считаю, что понимаю сейчас. Вот мои выводы и пересмотренный код:
Выводы:
- Самым большим виновником в моей первой попытке были 2 уравнения, которые начинались с "шагового пространства []" и "step char []". Согласование второго параметра шаговой функции с [] является no-no, поскольку он заставляет весь 2-й аргумент оцениваться (но с пояснением ниже).
- В какой-то момент я подумал, что (++) может оценить его правомерный аргумент позже, чем против, каким-то образом. Итак, я подумал, что могу исправить проблему, изменив "= (char: x): xs" to "= [ char: x] ++ xs". Но это было неверно.
- В какой-то момент я подумал, что шаблон, сопоставляющий второй аргумент arg (x: xs), приведет к сбою функции против бесконечных списков. Я был почти прав, но не совсем! Оценивая второй аргумент arg (x: xs), как и в предыдущем примере шаблона, вы получите некоторую рекурсию. Он "повернет кривошип" до тех пор, пока не ударит ":" (иначе, "минусы" ). Если бы этого не произошло, то моя функция не удалась бы против бесконечного списка. Однако в этом конкретном случае все в порядке, потому что моя функция в конечном итоге столкнется с пробелом, после чего произойдет "минус". И оценка, вызванная сопоставлением с (x: xs), остановится прямо там, избегая бесконечной рекурсии. В этот момент "x" будет сопоставлен, но xs останется тиком, поэтому проблем нет. (Спасибо Ганешу за то, что помогли мне понять это).
- В общем, вы можете указать второй аргумент, который вам нужен, если вы не оцениваете его силу. Если вы сопоставлены с x: xs, вы можете указать xs все, что хотите, если вы не принудительно оцениваете его.
Итак, здесь переработан код. Обычно я стараюсь избегать головы и хвоста, просто потому, что они являются частичными функциями, а также потому, что мне нужна практика написания эквивалента соответствия шаблону.
myWords :: String -> [String]
myWords string = foldr step [""] (dropWhile charIsSpace string)
where
step space acc | charIsSpace space = "":acc
step char (x:xs) = (char:x):xs
step _ [] = error "this should be impossible"
Это правильно работает против бесконечных списков. Обратите внимание, что в поле зрения нет оператора head, tail или (++).
Теперь, для важной оговорки: Когда я впервые написал исправленный код, у меня не было третьего уравнения, которое соответствует "step _ []". В результате я получил предупреждение о не исчерпывающих совпадениях шаблонов. Очевидно, что это хорошая идея, чтобы избежать этого предупреждения.
Но я думал, что у меня будет проблема. Я уже упоминал выше, что это не нормально, чтобы сопоставить второй аргумент против []. Но я должен был бы сделать это, чтобы избавиться от предупреждения.
Однако, когда я добавил уравнение "step_ []", все было в порядке! Не было никаких проблем с бесконечными списками!. Зачем?
Поскольку третье уравнение в исправленном коде НИКОГДА НЕ ДОСТИГЕТ!
На самом деле рассмотрим следующую версию BROKEN. Это ТОЧНО ТО ЖЕ, как правильный код, за исключением того, что я переместил шаблон для пустого списка выше других шаблонов:
myWords_brokenAgain :: String -> [String]
myWords_brokenAgain string = foldr step [""] (dropWhile charIsSpace string)
where
step _ [] = error "this should be impossible"
step space acc | charIsSpace space = "":acc
step char (x:xs) = (char:x):xs
Мы вернемся к переполнению стека, потому что первое, что происходит при вызове шага, - это то, что интерпретатор проверяет, соответствует ли уравнение номер один. Чтобы сделать это, он должен увидеть, является ли второй arg []. Для этого он должен оценить второй аргумент.
Перемещение уравнения вниз НИЖЕ других уравнений гарантирует, что третье уравнение никогда не будет пытаться, потому что всегда совпадает либо первый, либо второй паттерн. Третье уравнение просто состоит в том, чтобы отказаться от предупреждения об отсутствии исчерпывающего шаблона.
Это был отличный опыт обучения. Спасибо всем за вашу помощь.
