如何处理共同递归？

Question

好的,基本上我知道选项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但我也很欣赏一些关于共同递归的好解释的指示,以清除最后的疑惑:)

Answer 1

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

1. 在真正需要结果之前,不对事情进行评估;
2. 事情最多只评估一次.

这里的"事物"是"尚未评估的表达",也称为"thunk".

这是发生的事情:

你定义

naturals = 0 : map (+1) naturals

仅仅定义naturals并没有引入评估它的需要,所以最初naturals只会指出未评估表达式的一个thunk 0 : map (+1) naturals:

naturals = <thunk0>

在某些时候,你的程序可能会模仿自然的匹配.(模式匹配本质上是唯一强制在Haskell程序中进行评估的东西.)也就是说,你的程序需要知道自然是空列表还是头元素后跟尾列表.这是你定义的右侧将被评估,但只需要尽可能找出是否naturals是通过构造[]或(:):

naturals = 0 : <thunk1>

现在,自然会指向构造函数(:)在head元素上的应用,0以及仍未评估的尾部的thunk.(实际上,头部元素也将仍然没有评估,所以真的naturals会指向某种形式<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>).等等.