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

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

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

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

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

EDIT: Первоначально я думал, что проблема связана с тем, как ++ определяется в прелюдии, особенно с правилами перезаписи, поэтому вопрос продолжался, как показано ниже. Дискуссия показала мне, что это не так. Теперь я думаю, что некоторый ленивый эффект оценки заставляет код работать без, но я не совсем понимаю, как это сделать.

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

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

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

Ответ 1

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

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

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

Ключевое значение x : (xs ++ ys) - то есть рекурсия, охраняемая конструктором (:) "cons". Поскольку Haskell ленив, он выделяет thunk для операции cons, и рекурсивный вызов переходит на этот (выделенный кучей) thunk. Таким образом, выделение стека теперь представляет собой распределение кучи, которое может значительно расшириться. Таким образом, все это происходит по большому списку, выделяя новые объекты 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% времени на очистку узлов, созданных (++).

Урок: вы можете часто торговать стекю для кучи.

Ответ 2

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

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

Ответ 3

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

Если вы запустите ghc -ddump-simpl, вы увидите, что используемые функции GHC.Base.++ и GHC.List.reverse. Эти функции разработаны, чтобы не переполнять стек в больших списках. То, что вы видите в прелюдии, является "эталонной реализацией", а не кодом, который фактически скомпилирован.

Вот код, который я выкопал из дистрибутива 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
  #-}

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