haskell - 为什么这段 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

正如 chi 回答的那样，由于 cycle 的定义，您的代码在恒定空间中运行。

但是，即使使用 cycle xs = xs++ cycle xs，它也可以使用 ghc -O0 在常量空间中运行，因为顶级 thunk(常量应用形式，CAF -s) 可以被垃圾收集。闭包的信息表有“静态引用表”，它列出了静态闭包，这样

• 闭包的代码提到了它们
• 他们要么是顶级 thunk，要么他们的代码传递性地引用顶级 thunk

文档 here .如果无法从 GC 根(包括线程状态对象的堆栈，因此在我们的例子中是正在执行的 main 的闭包)到达顶级 thunk，它们指向的堆对象将被丢弃.