Coq：`PartialOrder` 类型类的用法

Question

我正在尝试在 poset 上定义字符串的字典顺序，但我不完全确定如何使用 PartialOrder 类型类。

Require Import List RelationClasses.

Fail Inductive lex_leq {A : Type} `{po : PartialOrder A} : list A -> list A -> Prop :=
  | lnil: forall l, lex_leq nil l
  | lcons: 
      forall (hd1 hd2 : A) (tl1 tl2 : list A),
        hd1 <= hd2 -> (* error *)
        (hd1 = hd2 -> lex_leq tl1 tl2) -> 
        lex_leq (hd1 :: tl1) (hd2 :: tl2).

部分输出：

The term "hd1" has type "A" while it is expected to have type "nat".

显然 <= 是这里使用的错误符号；我想知道如何从我的 po 实例中获得排序关系。

Answer 1

可以显式绑定名称以使事情更加明显。在我们这样做之前，我们需要告诉 Coq 不要使用 Generalizable Variables 命令抱怨未绑定变量：

From Coq Require Import List RelationClasses.

Generalizable Variables A eqA R.

Inductive lex_leq `{PartialOrder A eqA R} : list A -> list A -> Prop :=
  | lnil: forall l, lex_leq nil l
  | lcons: 
      forall (hd1 hd2 : A) (tl1 tl2 : list A),
        R hd1 hd2 ->
        (hd1 = hd2 -> lex_leq tl1 tl2) -> 
        lex_leq (hd1 :: tl1) (hd2 :: tl2).

您可以在手册中找到更多信息 (here)。

Coq：`PartialOrder` 类型类的用法

Coq: usage of `PartialOrder` typeclass

typeclass

coq