对具有非统一类型参数的数据类型进行归纳会产生错误类型的术语

Question

我正致力于在 Coq 中形式化 Free Selective Applicative Functors，但在使用非统一类型参数的归纳数据类型的归纳证明方面苦苦挣扎。

让我稍微介绍一下我正在处理的数据类型。在 Haskell 中，我们将 Free Selective Functors 编码为 GADT：

data Select f a where
    Pure   :: a -> Select f a
    Select :: Select f (Either a b) -> f (a -> b) -> Select f b

这里关键的是第二个数据构造函数中的存在类型变量b。

我们可以将这个定义翻译成 Coq：

Inductive Select (F : Type -> Type) (A : Set) : Set :=
    Pure   : A -> Select F A
  | MkSelect : forall (B : Set), Select F (B + A) -> F (B -> A) -> Select F A.

作为旁注，我使用 -impredicative-set 选项对其进行编码。

Coq 为该数据类型生成以下归纳原理：

Select_ind :
  forall (F : Type -> Type) (P : forall A : Set, Select F A -> Prop),
  (forall (A : Set) (a : A), P A (Pure a)) ->
  (forall (A B : Set) (s : Select F (B + A)), P (B + A)%type s ->
     forall f0 : F (B -> A), P A (MkSelect s f0)) ->
  forall (A : Set) (s : Select F A), P A s

这里，有趣的一点是谓词 P : forall A : Set, Select F A -> Prop，它不仅在表达式中被参数化，而且在表达式类型参数中也被参数化。据我了解，归纳原理之所以具有这种特殊形式，是因为 Select F (B + A).

类型的 MkSelect 构造函数的第一个参数

现在，我想为定义的数据类型证明类似第三条适用定律的陈述：

Theorem Select_Applicative_law3
        `{FunctorLaws F} :
  forall (A B : Set) (u : Select F (A -> B)) (y : A),
  u <*> pure y = pure (fun f => f y) <*> u.

其中涉及 Select F (A -> B) 类型的值，即包含函数的表达式。然而，对这种类型的变量调用 induction 会产生错误类型的术语。考虑一个可以通过 reflexivity 简单证明但不能使用 induction:

证明的等式的过度简化示例

Lemma Select_induction_fail `{Functor F} :
  forall (A B : Set) (a : A) (x : Select F (A -> B)),
    Select_map (fun f => f a) x = Select_map (fun f => f a) x.
Proof.
  induction x.

Coq 抱怨错误：

Error: Abstracting over the terms "P" and "x" leads to a term
fun (P0 : Set) (x0 : Select F P0) =>
  Select_map (fun f : P0 => f a) x0 = Select_map (fun f : P0 => f a) x0
which is ill-typed.
Reason is: Illegal application (Non-functional construction):
The expression "f" of type "P0" cannot be applied to the term
 "a" : "A"

在这里，Coq 无法构造在类型变量上抽象的谓词，因为语句的反向函数应用程序变得错误类型。

我的问题是，如何对我的数据类型使用归纳法？我看不出如何以这种方式修改归纳原则，使谓词不会抽象类型。我尝试使用 dependent induction，但它一直在产生受类似于 (A -> B -> C) = (X + (A -> B -> C)) 的等式约束的归纳假设，我认为这是不可能实例化的。

请参阅 GitHub 上的完整示例：https://github.com/tuura/selective-theory-coq/blob/impredicative-set/src/Control/Selective/RigidImpredSetMinimal.v

更新： 在 gist 中的讨论之后，我尝试通过对表达深度的归纳来进行证明。不幸的是，这条路并不是很有成果，因为我在类似于 Select_Applicative_law3 的定理中得到的归纳假设似乎无法使用。这个问题暂且搁置，稍后再试。

丽瑶，再次感谢你帮助我提高认识！

Answer 1

归纳证明的动机是递归定义。因此，要知道将归纳应用于什么，请查找 Fixpoints.

您的 Fixpoint 最有可能处理由单一类型变量 Select F A 索引的术语，这正是您要使用归纳法的地方，而不是在目标的顶层。

Fixpoint 由函数类型 A -> B 索引的术语是无用的，因为任何 Select 术语的子术语都没有被函数类型索引。出于同样的原因，induction 在这种情况下是无用的。

在这里，我认为强类型纪律实际上迫使你在尝试在 Coq 中做任何事情之前把所有事情都写在纸上（我认为这是一件好事）。尝试在纸上做证明，甚至不用担心类型；明确写下你想通过归纳法证明的谓词。这里有一个模板来理解我的意思：

By induction on u, we will show
 u <*> pure x = pure (fun f => f x) <*> u

    (* Dummy induction predicate for the sake of example. *)
    (* Find the right one. *)
    (* It may use quantifiers... *)
Base case (set u = Pure f). Prove:
Pure f <*> pure x = pure (fun f => f x) <*> Pure f
Induction step (set u = MkSelect v h). Prove:
MkSelect v h <*> pure x = pure (fun f => f x) <*> MkSelect v h
assuming the induction hypothesis for the subterm v (set u = v):
v <*> pure x = pure (fun f => f x) <*> v

特别注意最后一个等式是ill-typed，但你仍然可以运行连同它一起进行等式推理。无论如何，在简化目标后，很可能无法应用该假设。

如果你真的需要使用 Coq 做一些探索，有一个技巧，包括擦除有问题的类型参数（以及依赖它的所有术语）。根据您对 Coq 的熟悉程度，这个技巧可能比任何东西都更令人困惑。所以要小心。

术语仍将具有相同的递归结构。请记住，证明也应遵循相同的结构，因为重点是之后在顶部添加更多类型，因此您应该尽可能避免依赖类型缺失的快捷方式。

(* Replace all A and B by unit. *)
Inductive Select_ (F : unit -> Type) : Set :=
| Pure_ : unit -> Select_ F
| MkSelect_ : Select_ F -> F tt -> Select_ F
.

Arguments Pure_ {F}.
Arguments MkSelect_ {F}.

(* Example translating Select_map. The Functor f constraint gets replaced with a dummy function argument. *)
                                        (*      forall A B, (A -> B) -> (F A -> F B) *)
Fixpoint Select_map_ {F : unit -> Type} (fmap : forall t,   unit     -> (F t -> F t)) (f : unit -> unit) (v : Select_ F) : Select_ F :=
  match v with
  | Pure_ a => Pure_ (f a)
  | MkSelect_ w h => MkSelect_ (Select_map_ fmap f w) (fmap _ tt h)
  end.

这样，您就可以尝试证明这个精简版的函子定律，例如：

Select_map_ fmap f (Select_map_ fmap g v) = Select_map_ fmap (fun x => f (g x)) v

(* Original theorem:

Select_map f (Select_map g v) = Select_map (fun x => f (g x)) v

*)

重点是删除参数可以避免相关的打字问题，因此您可以天真地尝试使用归纳法来查看事情（不）如何解决。

对具有非统一类型参数的数据类型进行归纳会产生错误类型的术语

Induction on a datatype with non-uniform type parameters produces ill-typed terms

theorem-proving

coq