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

Question

在与my previous question相同的情况下，当我想出以下wrong函数试图连接累加器时，我尝试仅使用折叠实现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实现为折叠，仅将阶跃函数和种子作为自由度。

[在与上一个问题相同的情况下，当我想到以下错误的函数试图将....>]串联时，我尝试使用折叠仅实现循环函数¹。

foldr c n列出一个列表，并将每个(:)替换为c，最后一个[]替换为s。但是[1..]没有最终的[]，因此foldr (\_ a -> a ++ a) s没有放置s的位置。因此，没有信息从s到myCycle s的结果“流动”，这意味着它别无选择，只能是底层的（或者说：它有太多的选择，它的指定不充分，因此它放弃并退回到底部）。第二个版本实际上使用s，因为它出现在折叠功能中，当foldr作用于一个无限列表时，该折叠功能

is

使用。

实际上，我们具有身份

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

Answer 1

is