为什么recursion“让”使空间有效率？

我在学习function反应式编程的时候发现了这个说法，从刘海和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: rx r 3 -> 3: r 3 -> 3: 3: 3: ........ -> [3,3,3,......] 

如上所述，我们将需要为这些recursion创build无限的新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 

在第二种forms中，出现的xs可以在每个发生的地方共享，所以我想这就是为什么我们只需要O(1)空格而不是O(n) 。 但是我不确定我是否正确。

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

这里的问题是，标准的按需呼叫评估规则无法识别该function：

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

是相同的：

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

前者的定义使得对f的recursion调用重复工作，而在后一种情况下，计算是共享的。

Answer 1

用图片理解最简单：

• 第一个版本

   repeat x = x : repeat x 

  创build一个以(:)结尾的构造函数链，在你需要的时候会用更多的构造函数replace自己。 因此，O（n）空间。

  

• 第二个版本

   repeat x = let xs = x : xs in xs 

  使用let来“打结”，创build一个指向自己的单个(:)构造函数。

  

Answer 2

简而言之，variables是共享的，但function应用程序不是。 在

 repeat x = x : repeat x 

（从语言的angular度来说）重合的（共）recursion调用是一个巧合。 所以，没有额外的优化（称为静态参数转换），函数将被一次又一次地调用。

但是，当你写

 repeat x = let xs = x : xs in xs 

没有recursion函数调用。 你取一个x ，并用它构造一个循环值xs 。 所有的共享是明确的。

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

Answer 3

你对xs被分享的直觉是正确的。 要重复作者的例子重复，而不是整体，当你写：

 repeat x = x : repeat x 

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

 repeat x = let xs = x : xs in xs 

你明确地创build一个结构，当评估看起来像这样：

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