Почему этот код Haskell не исчерпывает кучу?

Question

Этот код суммирует содержимое двух (взаимно отмены) бесконечных списков, указанных на верхнем уровне:

{-# language BangPatterns #-} 
module Main where 

unending1 :: [Int] 
unending1 = cycle [1] 

unending2 :: [Int] 
unending2 = cycle [negate 1] 

main :: IO() 
main = do 
    let summator :: Int -> [Int] -> [Int] -> Int 
     summator !acc (i1 : rest1) (i2 : rest2) = 
      if acc > 100 
      then acc -- never happens 
      else summator (acc+i1+i2) rest1 rest2 
    print (summator 0 unending1 unending2) 

компилировать этот код без оптимизации и низкий размер кучи, как это:

ghc -O0 -with-rtsopts="-M10m" Main.hs 

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

Однако, когда я запускаю программу, она работает бессрочно без проблем.

Где я ошибаюсь?

---

Редактировать. Проверяя сгенерированное ядро ​​с использованием -ddump-simpl, списки, похоже, остаются на верхнем уровне. Например:

Result size of Tidy Core = {terms: 77, types: 52, coercions: 0} 

-- RHS size: {terms: 5, types: 3, coercions: 0} 
unending1 :: [Int] 
[GblId, Str=DmdType] 
unending1 = 
    cycle 
    @ Int (GHC.Types.: @ Int (GHC.Types.I# 1#) (GHC.Types.[] @ Int)) 

Answer 1

Как ответил чи, ваш код работает в постоянном пространстве из-за определения cycle.

Однако он работает в постоянном пространстве с ghc -O0 даже с cycle xs = xs ++ cycle xs, потому что верхние уровни thunks (постоянные аппликативные формы, CAF-s) могут быть собраны в мусор. В таблицах информации затворов имеют «статические справочные таблицы», перечень которых статические замыкания таким образом, что

• Код закрытия упоминает их
• Они либо санки верхнего уровня или их код транзитивно относится к сверху- уровень громкости

Документация here. Если верхние уровни не могут быть достигнуты из корней GC (включая стеки объектов состояния нитей, поэтому в нашем случае закрытие main), объекты кучи, на которые они указывают, отбрасываются.

Answer 2

От GHC.List:

cycle     :: [a] -> [a] 
cycle []    = errorEmptyList "cycle" 
cycle xs    = xs' where xs' = xs ++ xs' 

Обратите внимание, что рекурсия не включает в себя вызов функции, но значение в списке xs'.

При полном принуждении это должно быть представлено в памяти как круговой связанный список с обратным указателем. Тогда требуется только конечный объем памяти.

Попробуйте, например. Определение собственных cycle:

cycle' xs = xs ++ cycle' xs 

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

В самом деле, даже в GHCi (неоптимизированном), это остается под 70M на моей машине

> let list1 :: [Int] ; list1 = cycle [1,2,3] 
> list1 !! (4*10^9) 
2 

в то время как это взрывается (> 1 Гб):

> let list2 :: [Int] ; list2 = cycle' [1,2,3] 
> list2 !! (4*10^7) 
2