携带证明的归纳类型

Question

"Software Foundations" 中有一个练习，我已经尝试正确解决了一段时间，但实际上我在尝试写下所要求的函数方面遇到了困难。这是练习的相关部分

Consider a different, more efficient representation of natural numbers using a binary rather than unary system. That is, instead of saying that each natural number is either zero or the successor of a natural number, we can say that each binary number is either

zero,

twice a binary number, or

one more than twice a binary number.

(a) First, write an inductive definition of the type bin corresponding to this description of binary numbers.

朴素的定义并不完全有效，因为您最终能够构造项，将 1 加到已经加 1 的数字上，或者无缘无故地将 0 乘以 2。为了避免这些，我认为我会将某种状态转换编码到构造函数中以避免这些，但这有点棘手，所以这是我能想到的最好的方法

Inductive tag : Type := z | nz | m. (* zero | nonzero | multiply by 2 *)

Inductive bin_nat : tag -> Type :=
  (* zero *)
  | Zero : bin_nat z
  (* nonzero *)
  | One : bin_nat nz
  (* multiply by 2 -> nonzero *)
  | PlusOne : bin_nat m -> bin_nat nz
  (* nonzero | multiply by 2 -> multiply by 2 *)
  | Multiply : forall {t : tag}, (t = m \/ t = nz) -> bin_nat t -> bin_nat m.

通过上面的表示，我避免了没有意义的术语问题，但现在我每次乘以 2 时都必须携带证明。但实际上我不知道如何在递归函数中使用这些东西。

我知道如何构造证明和术语，它们看起来像这样

(* nonzero *)
Definition binr (t : tag) := or_intror (t = m) (eq_refl nz).
(* multiply by 2 *)
Definition binl (t : tag) := or_introl (t = nz) (eq_refl tag m).
(* some terms *)
Check Zero.
Check One.
Check (Multiply (binr _) One).
Check (Multiply (binl _) (Multiply (binr _) One)).
Check PlusOne (Multiply (binl _) (Multiply (binr _) One)).

我也可以写下一个"proof"的定理，我想对应一个函数，但是不知道怎么实际转换成函数。这是转换函数的证明

Definition binary_to_nat : forall t : tag, bin_nat t -> nat.
Proof.
intros.
einduction H as [ | | b | t proof b ].
  { exact 0. } (* Zero *)
  { exact 1. } (* One *)
  { exact (S (IHb b)). } (* PlusOne *)
  { (* Multiply *)
    edestruct t.
    cut False.
    intros F.
    case F.
    case proof.
    intros F.
    inversion F.
    intros F.
    inversion F.
    exact (2 * (IHb b)).
    exact (2 * (IHb b)).
  }
Defined.

我知道这个词是我想要的函数，因为我可以验证我在用它计算时得到了正确的答案

Section Examples.

Example a : binary_to_nat z Zero = 0.
Proof.
lazy.
trivial.
Qed.

Example b : binary_to_nat nz One = 1.
Proof.
lazy.
trivial.
Qed.

Example c : binary_to_nat m ((Multiply (binl _) (Multiply (binr _) One))) = 4.
Proof.
lazy.
trivial.
Qed.

End Examples.

那么最后的问题是，是否有一种简单的方法可以将上述证明项以简单的方式转换为实际函数，或者我是否必须尝试对证明项进行逆向工程？

Answer 1

我喜欢你使用状态和索引归纳类型表示有效二进制数的想法。然而，正如问题所指出的，归纳类型上仅使用三个构造函数是可能的：零、乘以 2 和乘以 2 加一。这意味着我们需要避免的唯一转换是将 0 乘以 2。

Inductive tag : Type := z | nz. (* zero | nonzero *)

Inductive bin_nat : tag -> Type :=
  (* zero *)
  | Zero : bin_nat z
  (* multiply by 2 *)
  | TimesTwo : bin_nat nz -> bin_nat nz
  (* multiply by 2 and add one *)
  | TimesTwoPlusOne : forall {t : tag}, bin_nat t -> bin_nat nz.

然后，例如，

Let One := TimesTwoPlusOne Zero. (* 1 *)
Let Two := TimesTwo One. (* 10 *)
Let Three := TimesTwoPlusOne One. (* 11 *)
Let Four := TimesTwo Two. (* 100 *)

所以TimesTwo在二进制表示的末尾添加一个零，TimesTwoPlusOne添加一个。

如果你想自己尝试这个，就不要再看了。

（我会把它放在剧透标签中，但显然剧透标签中的代码块有问题）

递增二进制数。

Fixpoint bin_incr {t: tag} (n: bin_nat t): bin_nat nz :=
match n with
| Zero => One
| TimesTwo n' => TimesTwoPlusOne n'
| @TimesTwoPlusOne _ n' => TimesTwo (bin_incr n')
end.

用于将 nat 转换为二进制的辅助定义。

Definition nat_tag (n: nat): tag :=
match n with
| 0 => z
| S _ => nz
end.

正在将 nat 转换为二进制。

Fixpoint nat_to_bin (n: nat): bin_nat (nat_tag n) :=
match n with
| 0 => Zero
| S n' => bin_incr (nat_to_bin n')
end.

正在将二进制转换为 nat。请注意，这使用了自然数的乘法和加法符号。如果这不起作用，您可能没有打开正确的范围。

Fixpoint bin_to_nat {t: tag} (n: bin_nat t): nat :=
match n with
| Zero => 0
| TimesTwo n' => 2 * (bin_to_nat n')
| @TimesTwoPlusOne _ n' => 1 + 2 * (bin_to_nat n')
end.

我们从这些定义中得到实际的功能（注意 20 在二进制中是 10100）。

Compute nat_to_bin 20.
= TimesTwo
     (TimesTwo (TimesTwoPlusOne (TimesTwo (TimesTwoPlusOne Zero))))
 : bin_nat (nat_tag 20)

Compute bin_to_nat (nat_to_bin 20).
= 20
 : nat

进一步的技术说明。我在 Coq 的两个版本（8.6 和 8.9+alpha）上使用了这段代码，一个版本要求我在匹配 TimesTwoPlusOne 时显式地放入标签，而另一个版本允许它保持隐式。上面的代码在任何一种情况下都应该有效。

携带证明的归纳类型

Inductive types carrying proofs

coq

logical-foundations