在 Coq 中为 coinductive 类型流定义一个 'head'（没有模式匹配）

Question

1) 我相信可以在没有模式匹配的情况下使用归纳类型。（仅使用 _rec、_rect、_ind）。它是不透明的、复杂的，但却是可能的。 2) 是否可以使用没有模式匹配的余归类型？

存在从余归类型到余归类型构造子域并集的函数。 Coq 是否显式生成它？如果是，如何重写 'hd' ?

Section stream.
  Variable A : Type.

  CoInductive stream : Type :=
  | Cons : A -> stream -> stream.
End stream.

Definition hd A (s : stream A) : A :=
  match s with
    | Cons x _ => x
  end.

Answer 1

虽然可以在不直接求助于模式匹配的情况下使用归纳类型，但这只是表面上的真实：Coq 生成的 _rec、_rect 和 _ind 组合子都是根据 match 定义。例如：

Print nat_rect.

nat_rect = 
fun (P : nat -> Type) (f : P 0) (f0 : forall n : nat, P n -> P (S n)) =>
fix F (n : nat) : P n :=
  match n as n0 return (P n0) with
  | 0 => f
  | S n0 => f0 n0 (F n0)
  end
     : forall P : nat -> Type,
       P 0 -> (forall n : nat, P n -> P (S n)) -> forall n : nat, P n

此外，在许多情况下，用消除器替换模式匹配会导致术语具有不同的计算行为。考虑以下函数，它将 nat 除以二：

Fixpoint div2 (n : nat) :=
  match n with
  | 0 | 1 => 0
  | S (S n') => S (div2 n')
  end.

可以使用 nat_rec 重写此函数，但对 n - 2 的递归调用使其有点复杂（试试吧！）。

现在，回到您的主要问题，Coq 不会自动为余归类型生成类似的消除原则。 Paco 库有助于推导出更有用的原则，用于推理关于余归数据。但据我所知，编写普通函数没有什么相似之处。

值得指出的是，您提出的方法与 Coq 对归纳数据类型所做的不同，因为 nat_rect 和朋友们允许通过归纳编写递归函数和证明。提供这些组合器的原因之一是它们被 induction 策略使用。 nat -> unit + nat 类型的内容或多或少与您提出的建议相对应，但还不够。

在 Coq 中为 coinductive 类型流定义一个 'head'（没有模式匹配）

Define a 'head' for coinductive type stream in Coq(without pattern matching)

coq

coinduction