为什么递归"让"让空间有效？

Question

我在研究功能反应式编程时发现了这一说法,来自Hai Liu和Paul Hudak的"用箭头堵塞空间泄漏"(第5页):

Suppose we wish to de?ne a function that repeats its argument inde?nitely:

    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).但我不确定我是否正确.

BTW:关键字"共享"来自同一篇论文的第4页:

这里的问题是标准的按需调用评估规则无法识别该功能:

f = ?dt ? integralC (1 + dt) (f dt) 

是相同的:

f = ?dt ? let x = integralC (1 + dt) x in x

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

Answer 1

用图片最容易理解:

• 第一个版本

  repeat x = x : repeat x
  

  创建一个(:)以thunk结尾的构造函数链,当你需要它时,它将用更多的构造函数替换它自己.因此,O(n)空间.

  

• 第二个版本

  repeat x = let xs = x : xs in xs
  

  用于let"打结",创建一个(:)引用自身的构造函数.

  

Answer 2

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

repeat x = x : repeat x

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

但是当你写作

repeat x = let xs = x : xs in xs

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

如果您想更正式地理解它,您需要熟悉惰性求值的语义,例如惰性评估的自然语义.

Answer 3

你对xs共享的直觉是正确的.在写作时重复作者的重复例子,而不是积分:

repeat x = x : repeat x

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

repeat x = let xs = x : xs in xs

你明确地创建了一个结构,当评估时看起来像这样:

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