Haskell 中的原始递归函数练习

Question

对于函数式编程练习，我需要在 haskell 中应用原始递归函数。不过我还不太明白这类函数的定义（和应用）。

我们给出了要使用的数据类型Nat，它的构造函数是： 数据 Nat = 零 |国家成功

根据我的理解，这意味着类型 "Nat" 可以是零或自然后继。

然后我们有一个递归：

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

我的理解是将递归应用于函数？

我还得到了一个使用递归的加法函数的例子：

addR :: Nat -> Nat -> Nat
addR m n = recNat n (\ _ y -> Succ y) m

但我不明白它是如何工作的，它使用给定的两个 Nats 的 recNat 函数，并且还使用匿名函数作为 recNat 的输入（这是我不确定它做什么的部分！ )

所以我的主要问题是它在函数中到底做了什么 > \ _ y -> Succ y

我应该应用相同的递归器 (RecNat) 将其他操作应用到 Nat，但我仍然试图理解这个例子！

Answer 1

粗略地说，recNat x f n 计算

f (n-1) (f (n-2) (f (n-3) (... (f 0 x))))

因此，它将 f 应用于 x n 次，每次还传递 "counter" 作为 f 的第一个参数。

在你的例子中 \_ y -> ... 忽略了 "counter" 参数。因此

addR m n = recNat n (\ _ y -> Succ y) m

可以读作"to compute m+n, apply m times the function Succ to n"。这有效地计算了 ((n+1)+1)+1...，其中总和中有 m 个。

您可以尝试以类似的方式计算两个自然数的乘积。使用 \_ y -> ... 并将乘法表示为重复加法。为此，您需要使用已经定义的 addR。

额外提示：乘法后，如果你想计算前导n-1，那么"counter"参数会很方便，所以不要丢弃它并使用\x y -> ...反而。之后，您可以将（截断的）减法导出为重复的前导。

Answer 2

你是对的 data Nat = Zero | Succ Nat 意味着 Nat 可能是 Zero 或另一个 Nat 的 Succ 继承人；这将自然数表示为链表，即：

zero, one, two, three, four, five :: Nat

zero  = Zero
one   = Succ Zero                              -- or: Succ zero
two   = Succ (Succ Zero)                       --     Succ one
three = Succ (Succ (Succ Zero))                --     Succ two
four  = Succ (Succ (Succ (Succ Zero)))         --     Succ three
five  = Succ (Succ (Succ (Succ (Succ Zero))))  --     Succ four
-- …

recNat的功能是折叠超过Nat：recNat z k取Nat并“倒数” 到最后的 Zero，在每个中间 Succ 上调用 k，并将 Zero 替换为 z:

recNat z k three
recNat z k (Succ (Succ (Succ Zero)))

-- by second equation of ‘recNat’:
k two                (recNat z k two)
k (Succ (Succ Zero)) (recNat z k (Succ (Succ Zero)))

-- by second equation of ‘recNat’:
k two                (k one         (recNat z k one))
k (Succ (Succ Zero)) (k (Succ Zero) (recNat z k (Succ Zero)))

-- by second equation of ‘recNat’:
k two                (k one         (k zero (recNat z k zero)))
k (Succ (Succ Zero)) (k (Succ Zero) (k Zero (recNat z k Zero)))

-- by first equation of ‘recNat’:
k two                (k one         (k zero z))
k (Succ (Succ Zero)) (k (Succ Zero) (k Zero z))

lambda \ _ y -> Succ y 的类型为 a -> Nat -> Nat；它只是忽略它的第一个参数和 returns 第二个参数的后继参数。这是 addR 如何计算两个 Nat 的总和的示例：

addR two three
addR (Succ (Succ Zero)) (Succ (Succ (Succ Zero)))

-- by definition of ‘addR’:
recNat three                     (\ _ y -> Succ y) two
recNat (Succ (Succ (Succ Zero))) (\ _ y -> Succ y) (Succ (Succ Zero))

-- by second equation of ‘recNat’:
(\ _ y -> Succ y) one         (recNat three                     (\ _ y -> Succ y) one)
(\ _ y -> Succ y) (Succ Zero) (recNat (Succ (Succ (Succ Zero))) (\ _ y -> Succ y) (Succ Zero))

-- by application of the lambda:
Succ (recNat three                     (\ _ y -> Succ y) one)
Succ (recNat (Succ (Succ (Succ Zero))) (\ _ y -> Succ y) (Succ Zero))

-- by second equation of ‘recNat’:
Succ ((\ _ y -> Succ y) zero (recNat three                     (\ _ y -> Succ y) zero))
Succ ((\ _ y -> Succ y) zero (recNat (Succ (Succ (Succ Zero))) (\ _ y -> Succ y) zero))

-- by application of the lambda:
Succ (Succ (recNat three                     (\ _ y -> Succ y) zero))
Succ (Succ (recNat (Succ (Succ (Succ Zero))) (\ _ y -> Succ y) zero))

-- by first equation of ‘recNat’:
Succ (Succ three)
Succ (Succ (Succ (Succ (Succ Zero))))

-- by definition of ‘five’:
five
Succ (Succ (Succ (Succ (Succ Zero))))

如您所见，这里发生的是我们实际上是从一个数字中取出每个 Succ 并将其放在另一个数字的末尾，或者等效地替换 Zero一个数字与另一个数字，即步骤如下：

1+1+0 + 1+1+1+0           2 + 3
1+(1+0 + 1+1+1+0)      1+(1 + 3)
1+1+(0 + 1+1+1+0)    1+1+(0 + 3)
1+1+(1+1+1+0)        1+1+(3)
1+1+1+1+1+0          5

内部 lambda 总是忽略它的第一个参数 _，所以通过更简单的 recNat 定义可以更简单地了解它是如何工作的，该定义将 Zero 逐字替换为值 z 和 Succ 具有函数 s:

recNat' :: a -> (a -> a) -> Nat -> a
recNat' z _ Zero     = z
recNat' z s (Succ n) = s (recNat z s n)

然后加法稍微简化：

addR' m n = recNat' n Succ m

字面上的意思是“要计算 m 和 n 的总和，将 m 次加到 n”。

如果您为它们创建一个 Num 实例和 Show 实例，您可能会发现使用这些数字更容易：

{-# LANGUAGE InstanceSigs #-}  -- for explicitness

instance Num Nat where

  fromInteger :: Integer -> Nat
  fromInteger n
    | n <= 0    = Zero
    | otherwise = Succ (fromInteger (n - 1))

  (+) :: Nat -> Nat -> Nat
  (+) = addR

  (*) :: Nat -> Nat -> Nat
  (*) = …  -- left as an exercise

  (-) :: Nat -> Nat -> Nat
  (-) = …  -- left as an exercise

  abs :: Nat -> Nat
  abs n = n

  signum :: Nat -> Nat
  signum Zero   = Zero
  signum Succ{} = Succ Zero

  negate :: Nat -> Nat
  negate n = n  -- somewhat hackish

instance Show Nat where
  show n = show (recNat' (+ 1) 0 n :: Int)

然后你可以写2 + 3 :: Nat并让它显示为5。

Haskell 中的原始递归函数练习

Primitive Recursive Functions Excercise in Haskell

recursion

primitive

haskell

function