Почему делает s ++ t не, приводят к переполнению стека для большого s?
Я задаюсь вопросом почему
Prelude> head $ reverse $ [1..10000000] ++ [99]
99
не приводит к ошибке переполнения стека. ++ во вводной части кажется прямым и non-tail-recursive:
(++) :: [a] -> [a] -> [a]
(++) [] ys = ys
(++) (x:xs) ys = x : xs ++ ys
Править: Первоначально, я думал, что проблема имеет некоторое отношение к пути ++, определяется во вводной части, особенно с правилами перезаписи, следовательно вопрос, продолженный как ниже. Обсуждение показало мне это дело обстоит не так. Я думаю теперь, когда некоторый эффект отложенных вычислений заставляет код работать без переполнения стека, но я не вполне фигурирую как.
Таким образом, только с этим, это должно столкнуться с переполнением стека, правильно? Таким образом, я полагаю, что это, вероятно, имеет некоторое отношение к ghc волшебству, которое следует определению ++:
{-# УПРАВЛЯЕТ "++" [~1] forall xs ys. xs ++ ys = приращение (\c n-> foldr c n xs) ys #-}
*Это, что помогает предотвращению переполнения стека? Кто-то мог обеспечить некоторую подсказку для того, что продолжается в этой части кода? **
3 ответа
При этом не происходит переполнения стека - даже в интерпретаторе, где нет оптимизаций и правил перезаписи, - потому что он не использует стек.
Взгляните на определение (++), например:
(++) :: [a] -> [a] -> [a]
(++) [] ys = ys
(++) (x:xs) ys = x : xs ++ ys
Ключевым моментом является x: (xs ++ ys) , то есть рекурсия охраняется ( :) "минусы" конструктора. Поскольку Haskell ленив, он выделяет преобразователь для операции cons, а рекурсивный вызов переходит в этот преобразователь (выделенный в куче). Таким образом, ваше выделение стека теперь является выделением кучи, которое может немного расшириться. Таким образом, все, что это делает, - это обход большого списка, размещение новых cons-объектов в куче для замены тех, по которым он проходит. Легкий!
"reverse" немного отличается:
reverse l = rev l []
where
rev [] a = a
rev (x:xs) a = rev xs (x:a)
Это хвостовая рекурсивная функция в стиле аккумулятора, поэтому, опять же, она будет размещаться в куче.
Как видите, функции полагаются на использование cons-ячеек в куче, а не в стеке, поэтому переполнение стека отсутствует.
Чтобы понять это, взгляните на статистику времени выполнения из GC vm:
$ time ./B +RTS -s
99
833 MB total memory in use (13 MB lost due to fragmentation)
Generation 0: 3054 collections, 0 parallel, 0.99s, 1.00s elapsed
%GC time 82.2% (85.8% elapsed)
Вот ваш большой список - он размещен в куче, и мы тратим 80% времени на очистку узлов cons, которые создаются (++).
Урок: часто можно обменять стек на кучу.
РЕДАКТИРОВАТЬ : ответ ниже совершенно неуместен, если не совершенно неверен. У Дона Стюарта, который демонстрирует, что он действительно понимает ленивую оценку, есть правильное объяснение.
Если вы запустите ghc -ddump-simple , вы увидите, что используются функции GHC.Base. ++ и GHC.List.reverse . Эти функции спроектированы так, чтобы не переполнять стек в больших списках. В Prelude вы видите «эталонную реализацию», а не код, который фактически скомпилирован.
Вот код, который я извлек из исходного дистрибутива GHC:
reverse :: [a] -> [a]
#ifdef USE_REPORT_PRELUDE
reverse = foldl (flip (:)) []
#else
reverse l = rev l []
where
rev [] a = a
rev (x:xs) a = rev xs (x:a)
#endif
И это:
(++) :: [a] -> [a] -> [a]
(++) [] ys = ys
(++) (x:xs) ys = x : xs ++ ys
{-# RULES
"++" [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs) ys
#-}
В первом случае должно быть ясно, что происходит. Во втором я немного не уверен в правилах перезаписи ...
++ в прелюдии кажется прямым и не хвостовым рекурсивным ... Значит, при этом он должен столкнуться с переполнением стека, не так ли?
Not-tail- Рекурсивный часто лучше, чем хвостовой рекурсивный в Haskell, потому что не хвостовые рекурсивные вещи могут быть ленивыми. Приведенное вами определение намного лучше, чем определение с хвостовой рекурсией, потому что определение с хвостовой рекурсией будет продолжать рекурсивно и генерировать весь список, даже если вам нужен только первый элемент; тогда как рекурсивный без хвоста будет делать столько работы, сколько необходимо.