是否可以在沒有前驅函數的基元遞歸中定義減法？

我有一個任務，我正在寫一堆基本的原始遞歸函數，其中一個是減法。我沒有獲得前任的定義，並認爲我不太可能將其定義爲eval Pred [x] = x-1。下面是我對PR的定義，我還定義了其他幾個函數，如時間，AND，OR，NOT，pow，true，false和ite。是否有可能只用我在這裏定義的減法？如果有的話可以給我一些指導。我目前的想法是我可以做類似的事情，給定minus[x,y]遞歸y次然後返回P 2。如果y > x我應該歸零。以下是我對PR的定義。是否可以在沒有前驅函數的基元遞歸中定義減法？

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])

編輯;我發現我的問題是定義正確的基本情況。 PR (P 3) (P 1)返回P 1 - 1，這是一個正確的方向，但是，我需要遞歸P 3次。我在想像PR (PR Z (P 3)) (P 1)這樣做。這當然是不正確的，但想法是從P 3到Z遞減，每次遞減P 1。

來源

2012-11-26 evanmcdonnal

我意識到這樣做的方法是使用PR來定義前驅。

pred = PR Z (P 1)

回報x-1或零，如果x = 0。

從那裏工作方法可如下

modus = C modus' [P 2, P 1] 
modus' = PR P 1 (C pred [P 2])

哪個遞歸遞減P 1P 2倍或定義直至P 1等於零。

來源

2012-11-26 06:51:19 evanmcdonnal

是否可以在沒有前驅函數的基元遞歸中定義減法？

回答

相關問題