У меня есть две функции Haskell, обе из которых кажутся мне очень похожими. Но первый не справляется с бесконечными списками, а второй - с бесконечными списками. Я часами пытался понять, почему это так, но безрезультатно.
Оба фрагмента представляют собой повторную реализацию функции "words" в 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 space []" и "step char []". Сопоставление второго параметра функции шага с [] - нет-нет , поскольку оно заставляет оценивать весь 2-й аргумент (но с оговоркой, поясняемой ниже).
- В какой-то момент я думал, что (++) может оценить свой правый аргумент позже, чем минусы, так или иначе. Итак, я подумал, что мог бы решить проблему, изменив "= (char: x): xs" на "= [char: x] ++ xs". Но это было неверно .
- В какой-то момент я подумал, что шаблон, соответствующий второму аргументу против (x: xs), вызовет сбой функции для бесконечных списков. Я был почти прямо об этом, но не совсем! Оценивая второй аргумент против (x: xs), как я делал в приведенном выше сопоставлении с шаблоном, WILL вызывает некоторую рекурсию. Он будет «поворачивать рукоятку», пока не достигнет «:» (иначе, «минусы»). Если этого никогда не произойдет, моя функция не будет работать с бесконечным списком. Тем не менее, , в данном конкретном случае , все в порядке, потому что моя функция в конечном итоге столкнется с пробелом, и в этот момент произойдут "минусы". И оценка, вызванная сопоставлением с (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"
Это правильно работает против бесконечных списков. Обратите внимание, что в поле зрения нет головы, хвоста или оператора (++).
Теперь для важного предостережения:
Когда я впервые написал исправленный код, у меня не было 3-го уравнения, которое соответствует «шагу _ []». В результате я получил предупреждение о неисчерпывающих совпадениях с образцами. Очевидно, это хорошая идея, чтобы избежать этого предупреждения.
Но я думал, что у меня будут проблемы. Я уже упоминал выше, что не в порядке сопоставления паттернов второго аргумента с [] . Но я должен сделать это, чтобы избавиться от предупреждения.
Однако, когда я добавил уравнение "step _ []", все было хорошо! По-прежнему не было проблем с бесконечными списками! . Зачем?
Поскольку 3-е уравнение в исправленном коде НИКОГДА НЕ ДОСТИГЛО!
На самом деле, рассмотрите следующую версию 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
Мы вернулись к переполнению стека, потому что первое, что происходит при вызове шага, это то, что интерпретатор проверяет, является ли уравнение номер один совпадением. Для этого он должен увидеть, является ли второй аргумент []. Для этого необходимо оценить второй аргумент.
Перемещение уравнения вниз НИЖЕ других уравнений гарантирует, что 3-е уравнение никогда не будет выполнено, потому что либо первый, либо второй шаблон всегда соответствуют . Третье уравнение просто для того, чтобы обойтись без неисчерпывающего предупреждения шаблона.
Это был большой опыт обучения. Спасибо всем за помощь.