为什么使用 fold 会产生一个指数增长的无限列表溢出？

Question

在与相同的情况下，我试图仅使用折叠实现 cycle 功能¹，当我想出以下 错误的 函数，它试图将累加器与自身连接起来，以指数方式构建无限列表（是的，我知道这意味着如果想要 take 1025，它会生成 2048 个副本其中）

myCycle :: [a] -> [a]
myCycle s = foldr (\_ a -> a ++ a) s [1..]

但是，使用它会抛出 *** Exception: heap overflow。

这个版本反而很有魅力

myCycle :: [a] -> [a]
myCycle s = foldr (\_ a -> s ++ a) s [1..]

我的问题是，为什么前一个版本会溢出，与后者相比？感觉理由比我还笨...

[1] 我的意思是，将 cycle 实现为一个折叠，只有阶跃函数和种子作为自由度。

Answer 1

foldr c n 获取一个列表，并将每个 (:) 替换为 c，最后的 [] 替换为 n。但是[1..]没有最后的[]，所以foldr (\_ a -> a ++ a) s没有地方放s。因此，从 s 到 myCycle s 的结果都没有 "flows" 的信息，这意味着它别无选择，只能处于底部（或者更确切地说：它有太多选择——它未指定——所以它放弃并跌回底部）。第二个版本其实确实用了s，因为它出现在折叠函数中，是当foldr作用于无限列表时使用

其实我们都有身份

foldr (\_ -> f) x xs = fix f = let x = f x in x

当 xs 为无限时。也就是说，foldr 的第二个参数在列表为无限时 完全被忽略 。此外，如果该折叠函数实际上并不查看列表的元素，那么真正发生的就是您在其自身内无限嵌套 f：fix f = f (f (f (f ...)))。 fix 是基本的，因为每种递归都可以用它来编写（某些更奇特的递归需要添加一些语言扩展，但定义 fix f = let x = f x in x 本身并没有改变）。这使得根据 foldr 和无限列表编写任何递归函数变得微不足道。

这是我对指数周期的看法。它产生 1 个输入副本，连接到 2 个副本，连接到 4 个副本，等等

myCycle xs = xs ++ myCycle (xs ++ xs)

通过将递归调用抽象为参数并将其传递给 fix:

，您可以将显式递归定义转换为 fix

myCycle = fix \rec xs -> xs ++ rec (xs ++ xs)

然后你使用 foldr 身份并引入一个伪造的 [] 案例

myCycle = foldr (\_ rec xs -> xs ++ rec (xs ++ xs)) (error "impossible") [1..]

为什么使用 fold 会产生一个指数增长的无限列表溢出？

Why using fold to generate an exponentially growing infinite list overflows?

haskell

fold