`list_rec` 的第一个输入什么时候不是常量函数?
When is the first input to `list_rec` not a constant function?
list_rec
函数的类型为:
list_rec
: forall (A : Type) (P : list A -> Set),
P nil ->
(forall (a : A) (l : list A), P l -> P (a :: l)%list) ->
forall l : list A, P l
在我提出的所有示例中,P
只是一个忽略输入列表的常量函数,无论如何 returns 都是相同的类型。例如,P
可能是 fun _ : list A => nat
或 fun _ : list A => list B
。使 P
的输出依赖于输入的一些用例是什么?为什么 P
的类型是 list A -> Set
而不是 Set
?
尝试证明s ++ [] = s
。
[提示:将 P
定义为 fun s => s ++ [] = s
。]
例如,我们可以使用 list_rec
和非常量 P
函数来实现将列表转换为向量(长度索引列表)的函数。
Require List Vector.
Import List.ListNotations Vector.VectorNotations.
Set Implicit Arguments.
Section VecExample.
Variable A : Set.
Definition P (xs : list A) : Set := Vector.t A (length xs).
Definition list_to_vector : forall xs : list A, Vector.t A (length xs) :=
list_rec P [] (fun x _ vtail => x :: vtail).
End VecExample.
您可以将其与以下代码中Vector.of_list
function, which does exactly the same (t
means Vector.t
的标准定义进行比较),使用显式递归而不是将其隐藏在递归原则之后:
Fixpoint of_list {A} (l : list A) : t A (length l) :=
match l as l' return t A (length l') with
|Datatypes.nil => []
|(h :: tail)%list => (h :: (of_list tail))
end.
一个简单的测试:
Eval compute in list_to_vector [1;2;3].
Eval compute in Vector.of_list [1;2;3].
两个函数调用return相同的结果:
= [1; 2; 3]
: Vector.t nat (length [1; 2; 3])
list_rec
函数的类型为:
list_rec
: forall (A : Type) (P : list A -> Set),
P nil ->
(forall (a : A) (l : list A), P l -> P (a :: l)%list) ->
forall l : list A, P l
在我提出的所有示例中,P
只是一个忽略输入列表的常量函数,无论如何 returns 都是相同的类型。例如,P
可能是 fun _ : list A => nat
或 fun _ : list A => list B
。使 P
的输出依赖于输入的一些用例是什么?为什么 P
的类型是 list A -> Set
而不是 Set
?
尝试证明s ++ [] = s
。
[提示:将 P
定义为 fun s => s ++ [] = s
。]
例如,我们可以使用 list_rec
和非常量 P
函数来实现将列表转换为向量(长度索引列表)的函数。
Require List Vector.
Import List.ListNotations Vector.VectorNotations.
Set Implicit Arguments.
Section VecExample.
Variable A : Set.
Definition P (xs : list A) : Set := Vector.t A (length xs).
Definition list_to_vector : forall xs : list A, Vector.t A (length xs) :=
list_rec P [] (fun x _ vtail => x :: vtail).
End VecExample.
您可以将其与以下代码中Vector.of_list
function, which does exactly the same (t
means Vector.t
的标准定义进行比较),使用显式递归而不是将其隐藏在递归原则之后:
Fixpoint of_list {A} (l : list A) : t A (length l) :=
match l as l' return t A (length l') with
|Datatypes.nil => []
|(h :: tail)%list => (h :: (of_list tail))
end.
一个简单的测试:
Eval compute in list_to_vector [1;2;3].
Eval compute in Vector.of_list [1;2;3].
两个函数调用return相同的结果:
= [1; 2; 3]
: Vector.t nat (length [1; 2; 3])