原始遞歸函數

Question

我試圖在Haskell中定義一些basic Primitive Recursive函數。爲什麼我的times函數遞歸太多次（即eval times[x,y]導致(x+1)*y）？我認爲我的問題通常是由於對組合函數的工作原理不瞭解。請不要在沒有解釋的情況下給出答案來澄清我的理解。

import Prelude hiding (pred,and,or,not) 

data PR = Z 
     | S 
     | P Int 
     | C PR [PR] 
     | PR PR PR 
     deriving Show 
eval :: PR -> [Integer] - Integer 
eval Z _ = 0 
eval S [x] = x+1 
eval (P n) xs = nth n xs 
eval (C f gs) xs = eval f (map (\g -> eval g xs) gs) 
eval (PR g h) (0:xs) = eval g xs 
eval (PR g h) (x:xs) = eval h ((x-1) : eval (PR g h) ((x-1):xs) : xs) 

nth _ [] = error "nth nil" 
nth 0 _ = error "nth index" 
nth 1 (x:_) = x 
nth (n) (_:xs) = nth (n-1) xs 

one = C S [Z] 
plus = PR (P 1) (C S [P 2]) 
times = PR (P 1) (C plus [P 2, P 3]) 

我已經嘗試了一些其他的事情times最接近的是times = PR (P 1) (C plus[P 2, P 2]但就出來2x*y我想：「嗯，我會剛剛取代那些P 2的與Z之一，那麼這將是x*y 「這實際上使其成爲y的身份識別功能，我不知道爲什麼。

Answer 1

此定義時間似乎工作：

times' = PR Z (C plus [P 2, P 3]) 

*Main> eval times' [6,7] 
42 

這是有道理的，因爲0 * * = 0而不是1

注意，我不得不改變的eval (C ...)的定義，以便爲它編譯：

eval (C f gs) cs = eval f (map (\g -> eval g cs) gs) 

更詳細的解釋...

我們知道times的形式爲PR Z h，其中一些h。

讓我們擴展eval (PR Z h) (x+1:y:ys) ...

eval (PR z h) (x+1:y:ys) 
    = eval h ((x+1-1) : eval (PR g h) ((x+1-1):y:ys) : y : ys) 
    = eval h (x : eval (PR Z h) (x:y:ys) : y : ys) 
    = eval h (x : x*y : y : ys) 

因爲通過歸納我們知道eval (PR z h) (x:y:ys) = x*y。

那麼h必須是爲了得到(x+1)*y = y+x*y？我們需要添加y（這是P 3）和x*y（這是P 2），所以我們應該定義h爲：

h = C plus [P 2, P 3] 

如果使用P 1代替Z，那麼你的基本情況是y而不是0：

eval (PR (P 1) ...) (0:y) = eval (P 1) (y) = y 

遞歸保持不變，所以你在回答中關閉了y。

Answer 2

假設op的形式爲PR something (C otherThing projections)。然後，如果x > 0，

eval op [x,y] 

電話

eval (C otherThing projections) [x-1, (x-1) `op` y, y] 

的otherThing越高排名op從構成操作。在更簡單的情況下，您只想調用遞歸調用y的結果(x-1) `op` y，因此投影應該選擇參數列表的第二個和第三個元素。

因此，我們有

times = PR something (C plus [P 2, P 3]) 

因爲我們有遞歸方程

x*y = (x-1)*y + y 

其不涉及分離的x-1。

現在，當達到基本情況x == 0時，遞歸調用應返回基本結果。對於乘法運算，當然是0，因此something應該是Z，獨立於y，而不是y，其中P 1會給你。

因此，user5402 said，你應該有

times = PR Z (C plus [P 2, P 3])