Почему s ++ t не приводит к переполнению стека для больших s?

Question

Мне интересно, почему

Prelude> head $ reverse $ [1..10000000] ++ [99]
99

не приводит к ошибке переполнения стека. ++ в прелюдии кажется прямым и нерекурсивным:

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

РЕДАКТИРОВАТЬ: Первоначально я думал, что проблема связана с тем, как ++ определяется в прелюдии, особенно с правилами переписывания, поэтому вопрос продолжался, как показано ниже. Дискуссия показала мне, что это не так. Теперь я думаю, что какой-то ленивый эффект оценки заставляет код работать без переполнения стека, но я не совсем понимаю, как.

Так вот, это должно привести к переполнению стека, верно? Поэтому я полагаю, что это, вероятно, связано с магией ghc, которая соответствует определению ++:

{- # ПРАВИЛА "++" [~ 1] для xs ys. xs ++ ys = augment (\ c n -> foldr c n xs) ys # -}

* Это то, что помогает избежать переполнения стека? Может ли кто-нибудь дать подсказку о том, что происходит в этом фрагменте кода? **

Answer 1

++ в прелюдии кажется прямым и нерекурсивным ... Так вот, это должно привести к переполнению стека, верно?

Не-хвостовая рекурсия часто лучше, чем хвостовая рекурсия в Хаскеле, потому что не хвостовая рекурсия может быть ленивой. Определение, которое вы перечислите там, намного лучше, чем определение с хвостовой рекурсией, потому что определение с хвостовой рекурсией продолжит рекурсивно и генерирует весь список, даже если вам нужен только первый элемент; тогда как нехвостый рекурсивный будет выполнять столько работы, сколько необходимо.

Answer 2

Это не переполняет стек - даже в интерпретаторе, где нет оптимизаций и правил перезаписи - потому что он не использует стек.

Посмотрите на определение (++), например:

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

Ключевым моментом является x : (xs ++ ys) - то есть рекурсия защищена конструктором (:) "cons". Поскольку Haskell ленив, он выделяет thunk для операции cons, и рекурсивный вызов переходит на этот (выделенный в куче) thunk. Таким образом, ваше выделение стека теперь является распределением кучи, которое может немного расшириться. Таким образом, все, что нужно сделать, - это пройтись по большому списку, распределить новые объекты cons в куче, чтобы заменить те, которые он обходит. Легко!

"реверс" немного отличается:

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% времени на очистку минусов, созданных (++).

Урок: вы часто можете обменять стек на кучу.

Answer 3

РЕДАКТИРОВАТЬ : Ответ, приведенный ниже, совершенно не имеет значения, если не прямо не так. Дон Стюарт, который демонстрирует, что он на самом деле понимает ленивая оценка, имеет правильное объяснение.

---

Если вы запустите ghc -ddump-simpl, вы увидите, что используются следующие функции: 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
  #-}

В первом случае должно быть ясно, что происходит. Во-вторых, я немного запутался в правилах переписывания ...