为什么递归“let”使空间有效率？ [英] Why recursive `let` make space effcient?

问题描述

我在研究Functional Reactive Programming时发现了这个声明，来自

 假设我们希望定义一个函数，它可以无限地重复它的参数：
 
 repeat x = x：repeat x 
 
或者在lambdas中：
 
 repeat =λx→x：重复x 
 
这需要O（n）空间。但是我们可以写成：
 
 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  - >让xs = x：xs in xs 
 r 3 
 
  - >让xs = 3：xs in xs 
  - > xs，根据上面的定义：
  - > 3：xs，其中xs = 3：xs 
  - > 3：xs：xs，其中xs = 3：xs 
  

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

BTW：关键词shared来自同一篇论文的第4页：

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

  f =λdt→integralC（1 + dt）（f dt）
  

与以下内容相同：

  f =λdt→let x = integralC（1 + dt）x in x 
  

前面的定义使得在递归调用
到f中重复工作，而在后一种情况下，计算是共享的。 p>

解决方案

第一个版本

 重复x = x：重复x 
  

创建一个以$结尾的（：）构造函数当你要求他们时，它会用更多的构造函数替换它自己。因此，O（n）空间。

  repeat x = let 
 

xs = x：xs in xs


使用让 totie the knot，创建一个指向它自己的（：）构造函数。
$ b

I found this statement while studying Functional Reactive Programming, from "Plugging a Space Leak with an Arrow" by Hai Liu and Paul Hudak ( page 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

The difference here seems small but it hugely prompts the space efficiency. Why and how it happens ? The best guess I've made is to evaluate them by hand:

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

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

As above, we will need to create infinite new thunks for these recursion. Then I try to evaluate the second one:

    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

In the second form the xs appears and can be shared between every places it occurring, so I guess that's why we can only require O(1) spaces rather than O(n). But I'm not sure whether I'm right or not.

BTW: The keyword "shared" comes from the same paper's page 4:

The problem here is that the standard call-by-need evaluation rules are unable to recognize that the function:

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

is the same as:

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

The former definition causes work to be repeated in the recursive call to f, whereas in the latter case the computation is shared.

解决方案

It's easiest to understand with pictures:

• The first version

  repeat x = x : repeat x
  

  creates a chain of (:) constructors ending in a thunk which will replace itself with more constructors as you demand them. Thus, O(n) space.

• The second version

  repeat x = let xs = x : xs in xs
  

  uses let to "tie the knot", creating a single (:) constructor which refers to itself.

这篇关于为什么递归“let”使空间有效率？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！