49

我在学习功能响应式编程时发现了这个声明，来自Hai Liu 和 Paul Hudak的“用箭头堵住空间泄漏” （第 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 的递归调用中重复工作，而在后一种情况下，计算是共享的。

4

3 回答 3

87

用图片最容易理解：

  • 第一个版本

    repeat x = x : repeat x

    创建一个(:)以 thunk 结尾的构造函数链，它将根据您的需要用更多构造函数替换自身。因此，O(n) 空间。

    一条链子

  • 第二个版本

    repeat x = let xs = x : xs in xs

    用于let“打结”，创建一个(:)引用自身的构造函数。

    一个循环

于 2013-05-19T07:35:11.653 回答
39

简而言之，变量是共享的，但函数应用程序不是。在

repeat x = x : repeat x

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

但是当你写

repeat x = let xs = x : xs in xs

没有递归函数调用。你取一个x, 并使用它构造一个循环值xs。所有共享都是明确的。

如果你想更正式地理解它，你需要熟悉惰性求值的语义，例如A Natural Semantics for Lazy Evaluation。

于 2013-05-19T07:31:44.290 回答
18

您对共享的直觉xs是正确的。当你写的时候，用重复而不是积分来重述作者的例子：

repeat x = x : repeat x

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

repeat x = let xs = x : xs in xs

您正在显式创建一个结构，在评估时看起来像这样：

{hd: x, tl:|}
^          |
 \________/
于 2013-05-19T07:32:32.573 回答