我可以在没有 let-binding 的情况下在 Coq 中进行“复杂的”相互递归吗?
Can I do “complex” mutual recursion in Coq without let-binding?
考虑以下一对相互递归的 Coq 数据类型,它们表示 Forest
个非空 Tree
。 Tree
的每个 Branch
都有一个额外的布尔标志,我们可以用 isOK
.
提取它
Inductive Forest a : Type
:= Empty : Forest a
| WithTree : Tree a -> Forest a -> Forest a
with Tree a : Type
:= Branch : bool -> a -> Forest a -> Tree a.
Arguments Empty {_}.
Arguments WithTree {_} _ _.
Arguments Branch {_} _ _ _.
Definition isOK {a} (t : Tree a) : bool :=
match t with
| Branch ok _ _ => ok
end.
现在,如果我们忽略这个布尔标志,我们可以编写一对映射函数来将一个函数应用于 Forest
或 Tree
中的每个值,这工作正常:
Fixpoint mapForest_always {a} (f : a -> a) (ts0 : Forest a) {struct ts0} : Forest a :=
match ts0 with
| Empty => Empty
| WithTree t ts => WithTree (mapTree_always f t) (mapForest_always f ts)
end
with mapTree_always {a} (f : a -> a) (t : Tree a) {struct t} : Tree a :=
match t with
| Branch ok x ts => Branch ok (f x) (mapForest_always f ts)
end.
但是,假设布尔值表示某种有效性检查,这在实际代码中会更复杂。所以我们首先检查布尔值,只有在必要时才实际递归。这意味着我们有 三个 相互递归函数,但其中一个只是在处理工作。不幸的是,这不起作用:
Fail Fixpoint mapForest_bad {a} (f : a -> a) (ts0 : Forest a) {struct ts0} : Forest a :=
match ts0 with
| Empty => Empty
| WithTree t ts => WithTree (mapTree_bad f t) (mapForest_bad f ts)
end
with mapTree_bad {a} (f : a -> a) (t : Tree a) {struct t} : Tree a :=
if isOK t
then mapOKTree_bad f t
else t
with mapOKTree_bad {a} (f : a -> a) (t : Tree a) {struct t} : Tree a :=
match t with
| Branch ok x ts => Branch ok (f x) (mapForest_bad f ts)
end.
问题是 mapTree_bad
调用 mapOKTree_bad
的参数实际上并不小。
除了... mapOKTree_bad
所做的只是一些预处理之后的额外步骤。这个 将 总是终止,但 Coq 看不到。为了说服终止检查器,我们可以改为定义 mapOKTree_good
,它是相同的但是是本地 let
绑定;然后,终止检查器将看穿 let
-binding 并允许我们定义 mapForest_good
和 mapTree_good
。如果我们想得到 mapOKTree_good
,我们可以在定义相互递归函数后使用一个普通的旧定义,它与 let
-binding:
具有相同的主体
Fixpoint mapForest_good {a} (f : a -> a) (ts0 : Forest a) {struct ts0} : Forest a :=
match ts0 with
| Empty => Empty
| WithTree t ts => WithTree (mapTree_good f t) (mapForest_good f ts)
end
with mapTree_good {a} (f : a -> a) (t : Tree a) {struct t} : Tree a :=
let mapOKTree_good {a} (f : a -> a) (t : Tree a) : Tree a :=
match t with
| Branch ok x ts => Branch ok (f x) (mapForest_good f ts)
end in
if isOK t
then mapOKTree_good f t
else t.
Definition mapOKTree_good {a} (f : a -> a) (t : Tree a) : Tree a :=
match t with
| Branch ok x ts => Branch ok (f x) (mapForest_good f ts)
end.
这行得通,但并不漂亮。有什么方法可以说服 Coq 的终止检查器接受 _bad
变体,或者 _good
技巧是我所拥有的最好的技巧吗?对我有用的命令,例如 Program Fixpoint
或 Function
,也是一个完全合理的解决方案。
非常片面的回答:我们可以重构 mapOKTree_good
的两个定义,在定义之前用 mapForest_good
参数化的中间定义。
Definition mapOKTree_good_ {a} mapForest_good
(f : a -> a) (t : Tree a) : Tree a :=
match t with
| Branch ok x ts => Branch ok (f x) (mapForest_good f ts)
end.
Fixpoint mapForest_good {a} (f : a -> a) (ts0 : Forest a) {struct ts0} : Forest a :=
match ts0 with
| Empty => Empty
| WithTree t ts => WithTree (mapTree_good f t) (mapForest_good f ts)
end
with mapTree_good {a} (f : a -> a) (t : Tree a) {struct t} : Tree a :=
if isOK t
then mapOKTree_good_ mapForest_good f t
else t.
Definition mapOKTree_good {a} := @mapOKTree_good_ a mapForest_good.
考虑以下一对相互递归的 Coq 数据类型,它们表示 Forest
个非空 Tree
。 Tree
的每个 Branch
都有一个额外的布尔标志,我们可以用 isOK
.
Inductive Forest a : Type
:= Empty : Forest a
| WithTree : Tree a -> Forest a -> Forest a
with Tree a : Type
:= Branch : bool -> a -> Forest a -> Tree a.
Arguments Empty {_}.
Arguments WithTree {_} _ _.
Arguments Branch {_} _ _ _.
Definition isOK {a} (t : Tree a) : bool :=
match t with
| Branch ok _ _ => ok
end.
现在,如果我们忽略这个布尔标志,我们可以编写一对映射函数来将一个函数应用于 Forest
或 Tree
中的每个值,这工作正常:
Fixpoint mapForest_always {a} (f : a -> a) (ts0 : Forest a) {struct ts0} : Forest a :=
match ts0 with
| Empty => Empty
| WithTree t ts => WithTree (mapTree_always f t) (mapForest_always f ts)
end
with mapTree_always {a} (f : a -> a) (t : Tree a) {struct t} : Tree a :=
match t with
| Branch ok x ts => Branch ok (f x) (mapForest_always f ts)
end.
但是,假设布尔值表示某种有效性检查,这在实际代码中会更复杂。所以我们首先检查布尔值,只有在必要时才实际递归。这意味着我们有 三个 相互递归函数,但其中一个只是在处理工作。不幸的是,这不起作用:
Fail Fixpoint mapForest_bad {a} (f : a -> a) (ts0 : Forest a) {struct ts0} : Forest a :=
match ts0 with
| Empty => Empty
| WithTree t ts => WithTree (mapTree_bad f t) (mapForest_bad f ts)
end
with mapTree_bad {a} (f : a -> a) (t : Tree a) {struct t} : Tree a :=
if isOK t
then mapOKTree_bad f t
else t
with mapOKTree_bad {a} (f : a -> a) (t : Tree a) {struct t} : Tree a :=
match t with
| Branch ok x ts => Branch ok (f x) (mapForest_bad f ts)
end.
问题是 mapTree_bad
调用 mapOKTree_bad
的参数实际上并不小。
除了... mapOKTree_bad
所做的只是一些预处理之后的额外步骤。这个 将 总是终止,但 Coq 看不到。为了说服终止检查器,我们可以改为定义 mapOKTree_good
,它是相同的但是是本地 let
绑定;然后,终止检查器将看穿 let
-binding 并允许我们定义 mapForest_good
和 mapTree_good
。如果我们想得到 mapOKTree_good
,我们可以在定义相互递归函数后使用一个普通的旧定义,它与 let
-binding:
Fixpoint mapForest_good {a} (f : a -> a) (ts0 : Forest a) {struct ts0} : Forest a :=
match ts0 with
| Empty => Empty
| WithTree t ts => WithTree (mapTree_good f t) (mapForest_good f ts)
end
with mapTree_good {a} (f : a -> a) (t : Tree a) {struct t} : Tree a :=
let mapOKTree_good {a} (f : a -> a) (t : Tree a) : Tree a :=
match t with
| Branch ok x ts => Branch ok (f x) (mapForest_good f ts)
end in
if isOK t
then mapOKTree_good f t
else t.
Definition mapOKTree_good {a} (f : a -> a) (t : Tree a) : Tree a :=
match t with
| Branch ok x ts => Branch ok (f x) (mapForest_good f ts)
end.
这行得通,但并不漂亮。有什么方法可以说服 Coq 的终止检查器接受 _bad
变体,或者 _good
技巧是我所拥有的最好的技巧吗?对我有用的命令,例如 Program Fixpoint
或 Function
,也是一个完全合理的解决方案。
非常片面的回答:我们可以重构 mapOKTree_good
的两个定义,在定义之前用 mapForest_good
参数化的中间定义。
Definition mapOKTree_good_ {a} mapForest_good
(f : a -> a) (t : Tree a) : Tree a :=
match t with
| Branch ok x ts => Branch ok (f x) (mapForest_good f ts)
end.
Fixpoint mapForest_good {a} (f : a -> a) (ts0 : Forest a) {struct ts0} : Forest a :=
match ts0 with
| Empty => Empty
| WithTree t ts => WithTree (mapTree_good f t) (mapForest_good f ts)
end
with mapTree_good {a} (f : a -> a) (t : Tree a) {struct t} : Tree a :=
if isOK t
then mapOKTree_good_ mapForest_good f t
else t.
Definition mapOKTree_good {a} := @mapOKTree_good_ a mapForest_good.