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

Question

在与 my previous question 相同的场景中，当我想出以下错误函数时，我试图仅使用折叠实现cycle函数¹，它试图连接累加器自身，以指数方式构建无限列表(是的，我知道这意味着如果想要获取其中的 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 ，这意味着它别无选择，只能处于底部(或者更确切地说:它有太多选择——未指定——所以它放弃并回到底部)。第二个版本实际上确实使用了 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..]