haskell - 共递归是如何处理的？

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

正如你所说，执行不会“糟糕”。 :) 懒惰的评估是你最好的 friend 。懒惰是什么意思？

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

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

发生的情况是这样的:

你定义

naturals = 0 : map (+1) naturals

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

naturals = <thunk0>

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

naturals = 0 : <thunk1>

这很自然，现在将指向构造函数 (:) 的应用程序在头部元素 0以及对尚未评估的尾部的重击。 (实际上， head 元素仍然未被评估，因此 naturals 实际上将指向 <thunk> : <thunk> 形式的某些内容，但我将忽略该细节。)

直到程序中稍后您可以在尾部进行模式匹配时，尾部的 thunk 才会被“强制”，即被评估。这意味着表达式 map (+1) naturals是要评估的。计算此表达式可减少为 map naturals 上的模式匹配:需要知道是否 naturals由 [] 构建或(:) 。我们看到，此时，naturals 不是指向一个 thunk，而是指向一个 thunk。已经指向 (:) 的应用程序，所以这个模式匹配 map无需进一步评估。应用map立即看到足够的naturals弄清楚它需要生成 (:) 的应用程序本身也是如此:map产生1 : <thunk2>其中 thunk 包含 map (+1) <?> 形式的未计算表达式。 (再说一遍，我们实际上没有 1 ，而是 0 + 1 的 thunk 。)什么是 <?>指向？嗯，naturals的尾部，这恰好是map正在生产。因此，我们现在有

naturals = 0 : 1 : <thunk2>

与<thunk2>包含尚未计算的表达式 map (+1) (1 : <thunk2>) .

在程序的稍后阶段，模式匹配可能会强制 <thunk2> ，这样我们就得到

naturals = 0 : 1 : 2 : <thunk3>

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