f# - 使用累加器在 F# 中对 Peano 数进行尾递归加法

Question

在 Uni，我们面临一个挑战，即使用累加器创建 Peano 数的尾递归加法。我们不允许使用任何库函数或我们创建的其他函数，但我们可以将累加器“隐藏”在辅助函数中

这是类型

  type Peano =
  | O
  | S of Peano

我被困在如何执行累加器上，因为它对定义的类型没有任何操作，即以下是不可能的

  let tailAdd p1 p2 =
    let rec aux p1 p2 acc =
      match p1, p2 with
        | O, _   -> acc
        | S v, b -> aux v b (acc + v)

  aux p1 p2 O

帮助 xD

Answer 1

我不想透露答案，因为这是一个家庭作业问题，但我会给你一个提示：在p1与 匹配的情况下S v，你知道v = p1 - 1。因此，p1 + p2 = v + (p2 + 1)。那么你如何p2 + 1用Peano数字写？

Answer 2

弄清楚了

let tailAdd p1 p2 = 
        let rec aux p1 p2 acc =
            match p1, p2 with
            | O, O   -> acc
            | a, S v -> aux v a (S (acc))
            | S v, b -> aux v b (S (acc))
        
        aux p1 p2 O