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)

我也在尝试实现指数函数，但似乎更加令人困惑。

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)