haskell - 原始递归函数

Question

在 A tutorial on universality and expressiveness of fold第 4.1 章指出了这种递归模式

h y [] = f y
h y (x:xs) = g y x xs (h y xs)

是原始递归，但我不明白为什么这个模式

h [] = v
h (x:xs) = g x (h xs)

不是根据 definition of primitive recursive 的原始递归.
h y'的值仍然基于h y在 h (x:xs) = g x (h xs)如果我们让y = xs和y' = x:xs .

Answer 1

原始递归方案是基于f,g选择的参数

h y [] = f y
h y (x:xs) = g y x xs (h y xs)

也就是说，我们可以随意选择f,g，而h将通过原始递归来定义。

特别是，我们可以选择

f = \y -> v
g = \y x xs -> g' x z

其中g'是我们选择的任何其他函数。然后我们得到

h y [] = v
h y (x:xs) = g' x (h y xs)

现在，如果我们让

h' xs = h () xs

我们将 y 参数修复为一个无关紧要的值，以便恢复问题中的函数。迂腐地，h' 并不是直接作为通用形式的实例获得的，因此 h' 在技术上并不是通过上面看到的原始递归方案来定义的(即，它不是一个例子)。有时，我们发现有许多变量 y1 .. yn 而不是 y，让我们可以选择 n=0 并删除 y 正如我们在本例中所希望的那样。