计算 Coq 列表中不同元素的数量
Counting number of different elements in a list in Coq
我正在尝试编写一个函数,该函数接受一个自然数列表,并 returns 作为输出其中不同元素的数量。例如,如果我有列表 [1,2,2,4,1],我的函数 DifElem 应该输出“3”。我已经尝试了很多东西,我得到的最接近的是:
Fixpoint DifElem (l : list nat) : nat :=
match l with
| [] => 0
| m::tm =>
let n := listWidth tm in
if (~ In m tm) then S n else n
end.
我的逻辑是:如果 m 不在列表的尾部,则向计数器加一。如果是,不要添加到计数器,所以我只会计算一次:当它最后一次出现时。我收到错误:
Error: The term "~ In m tm" has type "Prop"
which is not a (co-)inductive type.
In 是 Coq 列表标准库的一部分 Coq.Lists.List.
它在那里定义为:
Fixpoint In (a:A) (l:list A) : Prop :=
match l with
| [] => False
| b :: m => b = a \/ In a m
end.
我想我不太了解如何在定义中使用 If then 语句,Coq 的文档没有足够的帮助。
我还用来自同一个库的 nodup
尝试了这个定义:
Definition Width (A : list nat ) := length (nodup ( A ) ).
在这种情况下,我得到的错误是:
The term "A" has type "list nat" while it is expected to have
type "forall x y : ?A0, {x = y} + {x <> y}".
我对这里发生的事情感到很困惑。感谢您帮助解决这个问题。
您似乎混淆了命题 (Prop
) 和布尔值 (bool
)。我将尝试用简单的术语来解释:proposition 是你要证明的东西(根据 Martin-Lof 的解释,它是一组证明),而 boolean 是一种只能容纳 2 个值的数据类型 (true
/ false
)。当只有两种可能的结果并且不需要附加信息时,布尔值在计算中很有用。您可以在 this answer by @Ptival or a thorough section on this in the Software Foundations book by B.C. Pierce et al. (see Propositions and Booleans 部分找到有关此主题的更多信息。
实际上,nodup
是这里的方法,但 Coq 希望您提供一种确定输入列表元素是否相等的方法。如果你看一下 nodup
的定义:
Hypothesis decA: forall x y : A, {x = y} + {x <> y}.
Fixpoint nodup (l : list A) : list A :=
match l with
| [] => []
| x::xs => if in_dec decA x xs then nodup xs else x::(nodup xs)
end.
你会注意到一个假设decA
,它成为nodup
函数的附加参数,所以你需要传递eq_nat_dec
(nats
的可判定等式),例如,像这样:nodup eq_nat_dec l
.
所以,这是一个可能的解决方案:
Require Import Coq.Arith.Arith.
Require Import Coq.Lists.List.
Import ListNotations.
Definition count_uniques (l : list nat) : nat :=
length (nodup eq_nat_dec l).
Eval compute in count_uniques [1; 2; 2; 4; 1].
(* = 3 : nat *)
注意:nodup
函数自 Coq v8.5 起可用。
除了 Anton 使用标准库的解决方案之外,我想指出的是,mathcomp 为这个用例提供了特别好的支持以及关于 count
和 uniq
的非常完整的理论。您的函数变为:
From mathcomp Require Import ssreflect ssrfun ssrbool eqtype ssrnat seq.
Definition count_uniques (T : eqType) (s : seq T) := size (undup s).
其实我觉得count_uniques这个名字是多余的,我宁愿在需要的地方直接使用size (undup s)
。
使用集合:
Require Import MSets.
Require List. Import ListNotations.
Module NatSet := Make Nat_as_OT.
Definition no_dup l := List.fold_left (fun s x => NatSet.add x s) l NatSet.empty.
Definition count_uniques l := NatSet.cardinal (no_dup l).
Eval compute in count_uniques [1; 2; 2; 4; 1].
我正在尝试编写一个函数,该函数接受一个自然数列表,并 returns 作为输出其中不同元素的数量。例如,如果我有列表 [1,2,2,4,1],我的函数 DifElem 应该输出“3”。我已经尝试了很多东西,我得到的最接近的是:
Fixpoint DifElem (l : list nat) : nat :=
match l with
| [] => 0
| m::tm =>
let n := listWidth tm in
if (~ In m tm) then S n else n
end.
我的逻辑是:如果 m 不在列表的尾部,则向计数器加一。如果是,不要添加到计数器,所以我只会计算一次:当它最后一次出现时。我收到错误:
Error: The term "~ In m tm" has type "Prop"
which is not a (co-)inductive type.
In 是 Coq 列表标准库的一部分 Coq.Lists.List.
它在那里定义为:
Fixpoint In (a:A) (l:list A) : Prop :=
match l with
| [] => False
| b :: m => b = a \/ In a m
end.
我想我不太了解如何在定义中使用 If then 语句,Coq 的文档没有足够的帮助。
我还用来自同一个库的 nodup
尝试了这个定义:
Definition Width (A : list nat ) := length (nodup ( A ) ).
在这种情况下,我得到的错误是:
The term "A" has type "list nat" while it is expected to have
type "forall x y : ?A0, {x = y} + {x <> y}".
我对这里发生的事情感到很困惑。感谢您帮助解决这个问题。
您似乎混淆了命题 (Prop
) 和布尔值 (bool
)。我将尝试用简单的术语来解释:proposition 是你要证明的东西(根据 Martin-Lof 的解释,它是一组证明),而 boolean 是一种只能容纳 2 个值的数据类型 (true
/ false
)。当只有两种可能的结果并且不需要附加信息时,布尔值在计算中很有用。您可以在 this answer by @Ptival or a thorough section on this in the Software Foundations book by B.C. Pierce et al. (see Propositions and Booleans 部分找到有关此主题的更多信息。
实际上,nodup
是这里的方法,但 Coq 希望您提供一种确定输入列表元素是否相等的方法。如果你看一下 nodup
的定义:
Hypothesis decA: forall x y : A, {x = y} + {x <> y}.
Fixpoint nodup (l : list A) : list A :=
match l with
| [] => []
| x::xs => if in_dec decA x xs then nodup xs else x::(nodup xs)
end.
你会注意到一个假设decA
,它成为nodup
函数的附加参数,所以你需要传递eq_nat_dec
(nats
的可判定等式),例如,像这样:nodup eq_nat_dec l
.
所以,这是一个可能的解决方案:
Require Import Coq.Arith.Arith.
Require Import Coq.Lists.List.
Import ListNotations.
Definition count_uniques (l : list nat) : nat :=
length (nodup eq_nat_dec l).
Eval compute in count_uniques [1; 2; 2; 4; 1].
(* = 3 : nat *)
注意:nodup
函数自 Coq v8.5 起可用。
除了 Anton 使用标准库的解决方案之外,我想指出的是,mathcomp 为这个用例提供了特别好的支持以及关于 count
和 uniq
的非常完整的理论。您的函数变为:
From mathcomp Require Import ssreflect ssrfun ssrbool eqtype ssrnat seq.
Definition count_uniques (T : eqType) (s : seq T) := size (undup s).
其实我觉得count_uniques这个名字是多余的,我宁愿在需要的地方直接使用size (undup s)
。
使用集合:
Require Import MSets.
Require List. Import ListNotations.
Module NatSet := Make Nat_as_OT.
Definition no_dup l := List.fold_left (fun s x => NatSet.add x s) l NatSet.empty.
Definition count_uniques l := NatSet.cardinal (no_dup l).
Eval compute in count_uniques [1; 2; 2; 4; 1].