Почему 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 ( CN -> Foldr CN XS) YS # -}

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

Answer 1

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

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

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

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

«Реверс» немного отличается:

reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)

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

Таким образом, вы видите, функции полагаются на использование миновых клетков на куче, а не на стеке, поэтому без переполнения стека.

Чтобы действительно гвоздить это, посмотрите на статистика времени выполнения от VM GC:

$ 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 2

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

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

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
  #-}

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