17

好的，基本上我很难知道选项 1 或 2 是否适用于以下情况：

naturals = 0 : map (+ 1) naturals

选项有：
1. 执行很糟糕，每一步都重新计算所有内容：

naturals     = [0]
naturals'    = 0:map (+ 1) [0]          // == [0, 1]
naturals''   = 0:map (+ 1) [0, 1]       // == [0, 1, 2]
naturals'''  = 0:map (+ 1) [0, 1, 2]    // == [0, 1, 2, 3]
naturals'''' = 0:map (+ 1) [0, 1, 2, 3] // == [0, 1, 2, 3, 4]

2.执行并不糟糕，列表永远是无限的，map只应用一次

naturals     = 0:something
                                  |
naturals'    = 0:      map (+ 1) (0:      something)
                                    |
naturals''   = 0:1:    map (+ 1) (0:1:    something')
                                      |
naturals'''  = 0:1:2:  map (+ 1) (0:1:2:  something'')
                                        |
naturals'''' = 0:1:2:3:map (+ 1) (0:1:2:3:something''')

|指示其map执行的位置。

我确实知道答案可能只有1或2，但我也很感激一些关于共同递归的良好解释的指针，以消除最后的疑问:)

4

3 回答 3

32

正如你所说，执行不会是“可怕的”。:) 懒惰的评价是你最好的朋友。懒惰是什么意思？

  1. 在真正需要结果之前，不会对事物进行评估；
  2. 事物最多评估一次。

这里的“事物”是“尚未评估的表达式”，也称为“thunk”。

这是发生的事情：

你定义

naturals = 0 : map (+1) naturals

仅仅定义naturals并不需要评估它，所以最初naturals只会指向未评估表达式的 thunk 0 : map (+1) naturals：

naturals = <thunk0>

在某些时候，您的程序可能会在自然值上进行模式匹配。（模式匹配本质上是在 Haskell 程序中强制求值的唯一因素。）也就是说，您的程序需要知道 naturals 是空列表还是后跟一个尾列表的头元素。这是您定义的右侧将被评估的地方，但仅在需要找出是否naturals由[]or构造时(:)：

naturals = 0 : <thunk1>

这是 naturals 现在将指向构造函数(:)在 head 元素上的应用程序0和仍然未评估的尾部的 thunk。（实际上， head 元素也将是未评估的，因此确实naturals会指向 form 的某些内容<thunk> : <thunk>，但我将省略该细节。）

直到您的程序中的某个稍后点，您可以在尾部进行模式匹配，尾部的 thunk 才被“强制”，即评估。这意味着map (+1) naturals要计算表达式。评估这个表达式简化为对 的map模式匹配naturals：它需要知道是否naturals由[]或构造(:)。我们看到，此时，不是指向 thunk，naturals而是已经指向 的应用程序(:)，因此这种模式匹配map不需要进一步评估。的应用程序map确实立即看到足以naturals确定它需要生成(:)自身的应用程序，因此它确实：map生成1 : <thunk2>其中 thunk 包含表单的未计算表达式map (+1) <?>。（同样，1我们实际上有一个 thunk而不是0 + 1。）<?>指向什么？好吧， 的尾巴naturals，恰好map是产生的东西。因此，我们现在有

naturals = 0 : 1 : <thunk2>

包含<thunk2>尚未评估的表达式map (+1) (1 : <thunk2>)。

在您的程序的稍后时间点，模式匹配可能会强制<thunk2>，因此我们得到

naturals = 0 : 1 : 2 : <thunk3>

包含<thunk3>尚未评估的表达式map (+1) (2 : <thunk3>)。等等。

于 2012-04-21T08:38:11.140 回答
3

我花了一段时间才弄明白，但如果你想找到（比如说）第 10 亿个自然数，

n = nats !! 1000000000

您在 1+ 操作中遇到了 thunk 累积。我最终重写了（！！）：

nth (x:xs) n = if n==0 then x else x `seq` nth xs (n-1)

我尝试了几种方法来重写 nats 的定义以强制每个元素，而不是写 nth，但似乎没有任何效果。

于 2012-04-22T18:30:29.403 回答
1 
map f xs = f (head xs) : map f (tail xs)
p0 = 0 : map (+ 1) p0

-- when p0 is pattern-matched against:
p0 = "0" :Cons: "map (+ 1) {p0}"    
-- when (tail p0) is pattern-matched against:
-- {tail p0} := p1,
p1 = "(+ 1) (head {p0})" :Cons: "map (+ 1) (tail {p0})"       
-- when (tail p1) is pattern-matched against:
-- {tail p1} := p2,
p2 = "(+ 1) (head {p1})" :Cons: "map (+ 1) (tail {p1})"

Haskell 的列表很像 Prolog 的开放式列表，并且列表上的共同递归就像尾递归模 cons。一旦您实例化该 logvar - 从某个表达式设置列表的单元格值 - 它只是保持该值准备就绪，不再引用原始上下文。

naturals( [A|T] ):- T=[B|R], B=A+1, naturals( T ). % "=" sic! ("thunk build-up")

为了克服 Prolog 的严格性，我们让未来的访问驱动流程：

naturals( nats(0) ).
next( nats(A), A, nats(B) ):- 
  B is A+1.                    % fix the evaluation to be done immediately
take( 0, Next, Z-Z, Next).
take( N, Next, [A|B]-Z, NZ):- N>0, !, next(Next,A,Next1),
  N1 is N-1,                
  take(N1,Next1,B-Z,NZ).

Haskell 毫不费力地解决了这个问题，它的“存储”自然是惰性的（即列表构造函数是惰性的，并且列表构造只是通过访问“唤醒”，由语言的本质决定）。

使固定

比较这些：

fix f = f (fix f)         
fix f = x where x = f x   -- "co-recursive" fix ?

现在，当第一个定义用于以下内容时，您最初的担忧变成了现实：

g = fix $ (0:) . scanl (+) 1

它的经验复杂性实际上是二次的，或者更糟。但是对于第二个定义，它应该是线性的。

于 2012-06-03T22:17:02.733 回答