haskell - 为什么使用 fold 来生成指数增长的无限列表溢出？

Question

在与我之前的问题相同的场景中，我试图cycle仅使用折叠来实现该函数¹，当我想出以下错误函数时，它试图将累加器与自身连接起来，以指数方式构建无限列表（是的，我知道这意味着如果想要take1025 个副本，它会生成 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作为折叠实现，只有阶跃函数和种子作为自由度。

标签： haskellfold

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..]