function - 在haskell中实现原始递归阶乘

Question

我目前正在尝试在 Haskell 中实现原始递归阶乘。我正在使用函数 recNat 作为递归。那是：

recNat :: a -> (Nat -> a -> a) -> Nat -> a
recNat a _ Zero = a
recNat a h (Succ n) = h n (recNat a h n)

这是我们的尝试，但无法完全弄清楚出了什么问题

factR :: Nat -> Nat
factR Zero = Succ Zero
factR (Succ m) = recNat (Succ m) (\ _ y -> y) (factR m)

我也试图实现指数函数，但它似乎更令人困惑。

标签： functionhaskellrecursionprimitive

Answer 1

为了实现阶乘，我们可以实现一个乘法函数。对于乘法函数，我们需要加法函数

data Nat = Zero | Succ Nat

add :: Nat -> Nat -> Nat
add a Zero     = a
add a (Succ b) = Succ (add a b)

mul :: Nat -> Nat -> Nat
mul a Zero     = Zero
mul a (Succ b) = add a (mul a b)

那么阶乘函数就归结为：

fac :: Nat -> Nat
fac Zero = Succ Zero
fac (Succ a) = mul (Succ a) (fac a)