原始递归函数

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.
，

不是原始递归如果我们让 y = xs 和 y' = x:xs.

，h y' 的值仍然基于 h (x:xs) = g x (h xs) 中的 h y

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。

原始递归函数

Primitive Recursive function

haskell

recursion

functional-programming

fold