为什么“让”让空间变得高效？

Question

我在学习函数式反应性编程时发现了这句话，来自刘海和保罗·胡达克的《用箭堵住空间泄漏》（第5页）：

Suppose we wish to define a function that repeats its argument indefinitely:

    repeat x = x : repeat x

or, in lambdas:

    repeat = λx → x : repeat x

This requires O(n) space. But we can achieve O(1) space by writing instead:

    repeat = λx → let xs = x : xs
                  in xs

这里的差异似乎很小，但它极大地促进了空间效率。为什么以及如何发生？我最好的猜测是手工评估：

    r = \x -> x: r x
    r 3

    -> 3: r 3 
    -> 3: 3: 3: ........
    -> [3,3,3,......]

如上所述，我们需要为这些递归创建无限的新thunk。然后我尝试评估第二个：

    r = \x -> let xs = x:xs in xs
    r 3

    -> let xs = 3:xs in xs
    -> xs, according to the definition above: 
    -> 3:xs, where xs = 3:xs
    -> 3:xs:xs, where xs = 3:xs

在第二种形式中，出现了xs，并且可以在它出现的每个地方共享，所以我想这就是为什么我们只需要O（1）空格而不是O（n）。但是我不确定我是对还是错。

顺便说一句：关键词“共享”来自同一篇论文的第4页：

这里的问题是，标准的按需调用评估规则无法识别函数：

f = λdt → integralC (1 + dt) (f dt) 

是相同的：

f = λdt → let x = integralC (1 + dt) x in x

前一种定义导致在对f的递归调用中重复工作，而在后一种情况下，计算是共享的。

Answer 1

你对共享xs的直觉是正确的。当你写作时，用重复而不是整体的方式重述作者的例子：

repeat x = x : repeat x

该语言无法识别右侧的repeat x与表达式x:repeat x产生的值相同。如果你写

repeat x = let xs = x : xs in xs

您显式地创建了一个结构，在计算时如下所示：

{hd: x, tl:|}
^          |
 \________/

Answer 2

简单地说，变量是共享的，但函数应用程序不是。在里面

repeat x = x : repeat x

从语言的角度来看，（共同）递归调用repeat与同一个参数是巧合的。因此，如果没有额外的优化（称为静态参数转换），函数将被反复调用。

但是当你写作的时候

repeat x = let xs = x : xs in xs

没有递归函数调用。取一个x，用它构造一个循环值xs。所有的分享都是明确的。

如果你想更正式地理解它，你需要熟悉惰性评估的语义，比如惰性评估的自然语义。

Answer 3

用图片最容易理解：

>

第一个版本

repeat x = x : repeat x

创建一个以thunk结尾的（：）构造函数链，它将根据您的要求用更多构造函数替换自己。因此，O（n）空间。

https://imgs.xnip.cn/cj/n/85/ba05b47a-64f9-46f8-a2a6-922c83ef3715.png" width="100%" height="100%" />

第二个版本

repeat x = let xs = x : xs in xs

使用let来"喜结连理"，创建一个引用自身的（：）构造函数。