在匹配项中展开类型函数(如 destruct)
Unfold a type-function in a match (like destruct)
TL;DR
我想编写一个固定点定义,在没有证明模式的情况下匹配依赖类型中的一个值。本质问题是 Coq 不会使用 match
来注意到依赖类型中的类型是等价的;我可以强制它进入验证模式,但我想知道如果没有它是否可以这样做。
我正在从事一个涉及大量矩阵运算的项目。矩阵可以是任意多维的(每个都是矩形的),所以我写了一个定义来计算矩阵的类型:
Require Import Coq.Unicode.Utf8.
Require Export Vector.
Import VectorNotations.
Require Import List.
Import ListNotations.
Fixpoint matrix (A: Type) (dims: list nat) :=
match dims with
| [] => A
| head::tail => Vector.t (matrix A tail) head
end.
出于“原因”,我需要对元素进行线性化,以便 select 线性化矩阵的第 n 个元素。我的第一次尝试是尝试 return 一维矩阵,但我 运行 与 List 的 fold_left
撞墙(不胜感激):
Definition product (dims: list nat) := List.fold_left Nat.mul dims 1.
Definition linearize {A: Type} {dims: list nat} (m: matrix A dims): matrix A [product dims].
Proof.
generalize dependent m.
induction dims.
- intros.
assert (product [] = 1) by reflexivity. rewrite H; clear H.
exact (Vector.cons A m 0 (Vector.nil A)).
- intros.
(* why so hard? *)
assert (product (a::dims) = a * product dims).
{ unfold product.
assert (a::dims = [a] ++ dims) by reflexivity. rewrite H; clear H.
rewrite List.fold_left_app.
assert (List.fold_left Nat.mul [a] 1 = a). admit. }
Abort.
我认为转换为列表可能更容易,所以:
Fixpoint linearize' {A: Type} {dims: list nat} (m: matrix A dims): list A :=
match dims with
| [] => []
| h::t => Vector.fold_left
(@app A)
[]
(Vector.map linearize' (m: Vector.t (matrix (list A) t) h))
end.
但是 Coq 抱怨:
In environment
linearize' : ∀ (A : Type) (dims : list nat), matrix A dims → list A
A : Type
dims : list nat
m : matrix A dims
h : nat
t : list nat
The term "m" has type "matrix A dims" while it is expected to have type
"Vector.t (matrix (list A) t) h".
我能够使用“证明风格”来编写定义,但令我困惑的是我无法让 Coq 接受本质上相同的定点!
Definition linearize {A: Type} {dims: list nat} (m: matrix A dims): list A.
Proof.
induction dims.
- (* unfold matrix in m. *) (* exact [m]. *) apply [m].
- simpl in m.
(* exact (Vector.fold_left (@List.app A) [] (Vector.map IHdims m)). *)
apply (Vector.map IHdims) in m.
apply (Vector.fold_left (@List.app A) [] m).
Defined.
似乎如果我能让 Coq 破坏 m
和 dims
的类型,就像在归纳法中发生的那样,我会很高兴去……这里是 Print linearize.
linearize =
λ (A : Type) (dims : list nat) (m : matrix A dims),
list_rect (λ dims0 : list nat, matrix A dims0 → list A)
(λ m0 : matrix A [], [m0])
(λ (a : nat) (dims0 : list nat) (IHdims : matrix A dims0 → list A)
(m0 : matrix A (a :: dims0)),
let m1 := Vector.map IHdims m0 in Vector.fold_left (app (A:=A)) [] m1)
dims m
: ∀ (A : Type) (dims : list nat), matrix A dims → list A
Arguments linearize {A}%type_scope {dims}%list_scope _
这是在 Coq 中使用依赖类型的主要难题之一。解决办法是重写linearize,使其returns匹配后成为一个函数:
Require Import Coq.Unicode.Utf8.
Require Export Vector.
Import VectorNotations.
Require Import List.
Import ListNotations.
Fixpoint matrix (A: Type) (dims: list nat) :=
match dims with
| [] => A
| head::tail => Vector.t (matrix A tail) head
end.
Fixpoint linearize {A: Type} {dims: list nat} : matrix A dims -> list A :=
match dims with
| [] => fun _ => []
| dim :: dims => fun mat =>
let res := Vector.map (@linearize _ dims) mat in
Vector.fold_left (@app _) [] res
end.
这个技巧被称为护航模式;您可以在这里找到更多相关信息:http://adam.chlipala.net/cpdt/html/MoreDep.html .
我的第一反应是“List.fold_left
,他会过得很糟糕。”
这里有一个使用 List.fold_right
的解决方案。
Definition product (dims: list nat) := List.fold_right Nat.mul 1 dims.
Fixpoint concat {A} {n m : nat} (v : Vector.t (Vector.t A m) n) : Vector.t A (n * m) :=
match v with
| []%vector => []%vector
| (x :: xs)%vector => append x (concat xs)
end.
Fixpoint linearize {A: Type} {dims: list nat} : matrix A dims -> matrix A [product dims] :=
match dims with
| [] => fun a => (a :: [])%vector
| head :: tail => fun a => concat (Vector.map (linearize (dims := tail)) a)
end.
fold_left
的问题在于,在非空情况下,它展开为立即递归调用,这为依赖类型的编程隐藏了太多信息。一个用例可能是定义尾递归函数,但这在这里不适用。
使用 fold_right
,每当您在 dims
上进行模式匹配时,cons
情况就会暴露一个 Nat.mul
,它允许使用 concat : Vector.t (Vector.t A m) n -> Vector.t A (n * m)
。
TL;DR
我想编写一个固定点定义,在没有证明模式的情况下匹配依赖类型中的一个值。本质问题是 Coq 不会使用 match
来注意到依赖类型中的类型是等价的;我可以强制它进入验证模式,但我想知道如果没有它是否可以这样做。
我正在从事一个涉及大量矩阵运算的项目。矩阵可以是任意多维的(每个都是矩形的),所以我写了一个定义来计算矩阵的类型:
Require Import Coq.Unicode.Utf8.
Require Export Vector.
Import VectorNotations.
Require Import List.
Import ListNotations.
Fixpoint matrix (A: Type) (dims: list nat) :=
match dims with
| [] => A
| head::tail => Vector.t (matrix A tail) head
end.
出于“原因”,我需要对元素进行线性化,以便 select 线性化矩阵的第 n 个元素。我的第一次尝试是尝试 return 一维矩阵,但我 运行 与 List 的 fold_left
撞墙(不胜感激):
Definition product (dims: list nat) := List.fold_left Nat.mul dims 1.
Definition linearize {A: Type} {dims: list nat} (m: matrix A dims): matrix A [product dims].
Proof.
generalize dependent m.
induction dims.
- intros.
assert (product [] = 1) by reflexivity. rewrite H; clear H.
exact (Vector.cons A m 0 (Vector.nil A)).
- intros.
(* why so hard? *)
assert (product (a::dims) = a * product dims).
{ unfold product.
assert (a::dims = [a] ++ dims) by reflexivity. rewrite H; clear H.
rewrite List.fold_left_app.
assert (List.fold_left Nat.mul [a] 1 = a). admit. }
Abort.
我认为转换为列表可能更容易,所以:
Fixpoint linearize' {A: Type} {dims: list nat} (m: matrix A dims): list A :=
match dims with
| [] => []
| h::t => Vector.fold_left
(@app A)
[]
(Vector.map linearize' (m: Vector.t (matrix (list A) t) h))
end.
但是 Coq 抱怨:
In environment
linearize' : ∀ (A : Type) (dims : list nat), matrix A dims → list A
A : Type
dims : list nat
m : matrix A dims
h : nat
t : list nat
The term "m" has type "matrix A dims" while it is expected to have type
"Vector.t (matrix (list A) t) h".
我能够使用“证明风格”来编写定义,但令我困惑的是我无法让 Coq 接受本质上相同的定点!
Definition linearize {A: Type} {dims: list nat} (m: matrix A dims): list A.
Proof.
induction dims.
- (* unfold matrix in m. *) (* exact [m]. *) apply [m].
- simpl in m.
(* exact (Vector.fold_left (@List.app A) [] (Vector.map IHdims m)). *)
apply (Vector.map IHdims) in m.
apply (Vector.fold_left (@List.app A) [] m).
Defined.
似乎如果我能让 Coq 破坏 m
和 dims
的类型,就像在归纳法中发生的那样,我会很高兴去……这里是 Print linearize.
linearize =
λ (A : Type) (dims : list nat) (m : matrix A dims),
list_rect (λ dims0 : list nat, matrix A dims0 → list A)
(λ m0 : matrix A [], [m0])
(λ (a : nat) (dims0 : list nat) (IHdims : matrix A dims0 → list A)
(m0 : matrix A (a :: dims0)),
let m1 := Vector.map IHdims m0 in Vector.fold_left (app (A:=A)) [] m1)
dims m
: ∀ (A : Type) (dims : list nat), matrix A dims → list A
Arguments linearize {A}%type_scope {dims}%list_scope _
这是在 Coq 中使用依赖类型的主要难题之一。解决办法是重写linearize,使其returns匹配后成为一个函数:
Require Import Coq.Unicode.Utf8.
Require Export Vector.
Import VectorNotations.
Require Import List.
Import ListNotations.
Fixpoint matrix (A: Type) (dims: list nat) :=
match dims with
| [] => A
| head::tail => Vector.t (matrix A tail) head
end.
Fixpoint linearize {A: Type} {dims: list nat} : matrix A dims -> list A :=
match dims with
| [] => fun _ => []
| dim :: dims => fun mat =>
let res := Vector.map (@linearize _ dims) mat in
Vector.fold_left (@app _) [] res
end.
这个技巧被称为护航模式;您可以在这里找到更多相关信息:http://adam.chlipala.net/cpdt/html/MoreDep.html .
我的第一反应是“List.fold_left
,他会过得很糟糕。”
这里有一个使用 List.fold_right
的解决方案。
Definition product (dims: list nat) := List.fold_right Nat.mul 1 dims.
Fixpoint concat {A} {n m : nat} (v : Vector.t (Vector.t A m) n) : Vector.t A (n * m) :=
match v with
| []%vector => []%vector
| (x :: xs)%vector => append x (concat xs)
end.
Fixpoint linearize {A: Type} {dims: list nat} : matrix A dims -> matrix A [product dims] :=
match dims with
| [] => fun a => (a :: [])%vector
| head :: tail => fun a => concat (Vector.map (linearize (dims := tail)) a)
end.
fold_left
的问题在于,在非空情况下,它展开为立即递归调用,这为依赖类型的编程隐藏了太多信息。一个用例可能是定义尾递归函数,但这在这里不适用。
使用 fold_right
,每当您在 dims
上进行模式匹配时,cons
情况就会暴露一个 Nat.mul
,它允许使用 concat : Vector.t (Vector.t A m) n -> Vector.t A (n * m)
。