问Haskell非函数递归(或值递归或递归let绑定)

EN

在许多(大多数？)语言函数是一种“特殊”的值，在语言语法和语义上具有特殊的地位。

在哈斯克尔，没那么多。它们与非函数共享许多属性。特别是：

• 我们可以将函数(和非函数)作为参数传递给函数。
• 我们可以从函数返回函数(和非函数)。
• 我们可以将函数(和非函数)放入容器中，如列表、对等。
• 我们可以递归地定义函数(和非函数)。

如果您不习惯，最后一点可能会令人费解，但是没有理由只在像Haskell这样的惰性语言中定义函数值时才允许递归。

例如，可以通过允许1:1:1:....来定义无限列表list = 1 : list。如果您只能理解函数的递归定义，只需知道它与list() = 1 : list()类似，除非list不是一个函数，而是一个列表。

您还可以尝试理解1:2:3:4:....可以递归地定义为list = 1 : map (+1) list。事实上，展开我们得到的定义：

list
= 1 : map (+1) list
= 1 : map (+1) (1 : map (+1) list)
= 1 : 2 : map (+1) (map (+1) list)
= 1 : 2 : map (+1) (map (+1) (1 : map (+1) list))
= 1 : 2 : 3 : map (+1) (map (+1) (map (+1) list))
...

请注意，上面的定义“工作”是因为它可以在递归地需要自己的值之前生成值的一部分。在您提到的i = i + 1示例中，这种情况不会发生，因为i + 1需要立即获得i的值，然后才能生成输出的任何部分。(至少在标准整数类型上是这样的。)因此，它具有与无限递归函数(如i() = i() + 1 )相同的行为。