ペアとリスト
前のパートでは、新しいデータ型を設定し、それらの上に関数を定義し、一般的な戦術を使用してその正確性を証明する方法を学びました。 いくつかのデータ構造とそれらの上に高次関数（以降FWP）を定義する時が来ました。
帰納的定義では、各コンストラクターに任意の数のパラメーター、たとえば定義を含めることができます
誘導ナットプロッド：タイプ：=
ペア：nat-> nat-> natprod。
次のように読みます：数値のペアを作成する方法は1つだけです-
pairコンストラクターを
nat型の2つの引数に適用
Eval simpl in（ペア1 2）。
（* ==>ペア1 2：natprod *）
Coqには、
Notationコマンドを使用して構文糖を注入するメカニズムがあります。 たとえば、プレフィックス形式を削除して、次のような数字のペアを定義できます。
表記 "（x、y）"：=（ペアxy）。
この新しい表記法は、式、関数の定義、定理の記述で広く使用できます。
定義fst（p：natprod）：nat：=
pと一致
| （x、y）=> x
終わり。
定義snd（p：natprod）：nat：=
pと一致
| （x、y）=> y
終わり。
定理検定：forall（ab：nat）、
（a、b）=（fst（a、b）、snd（a、b））。
証明。 反射性。 Qed。
ペアの定義を要約すると、数字のリストを記述することもできます。
誘導natlist：タイプ：=
| nil：natlist
| 短所：nat-> natlist-> natlist。
表記 "h :: t"：=（cons ht）（レベル60、右結合性）。
表記「[]」：= nil。
表記 "[h、..、t]"：=（cons h ..（cons t nil）..）。
導入された構文規則を使用して、リストをいくつかの方法で定義できます。
定義リスト1：= 1 ::（2 ::（3 :: nil））。
定義リスト2：= [1,2,3]。
リストは、関数型プログラミング言語で広く使用されています。 しかし、一般化された定義を使用して整数のリスト、論理値のリストを作成する場合はどうでしょうか？ Coqには、ポリモーフィックな帰納的型を定義するメカニズムがあります。
帰納的リスト（X：タイプ）：タイプ：=
| nil：リストX
| 短所：X->リストX->リストX。
ここでの
nilと
consは、ポリモーフィックコンストラクターの役割を果たします。 同様に、ポリモーフィック関数を定義できます。
FVP
フィルター
現代の多くのプログラミング言語では、関数は別の関数を引数として受け入れるか、結果として返すことができます。 このような関数は高次関数と呼ばれ、数学（微分計算演算子など）およびプログラミング（
filter関数が述語によってセットの要素をフィルター
filterするなど）で広く使用されてい
filter 。
Fixpoint evenb（n：nat）：bool：=
nに一致
| O => true
| SO => false
| S（S n '）=>偶数b n'
終わり。
固定小数点フィルター{X：タイプ}（テスト：X→bool）（l：リストX）
：（リストX）：=
と一致l
| [] => []
| h :: t => if test h then h ::（filter test t）
その他のフィルタテストt
終わり。
テスト例：フィルターevenb [1,2,3,4,5] = [2,4]。
証明。 反射性。 Qed。
地図
FVP
mapは、この関数をリストの各要素に適用し、結果のリストを返します。
固定点マップ{XY：タイプ}（f：X→Y）（l：リストX）
：（リストY）：=
と一致l
| [] => []
| h :: t =>（fh）::（map ft）
終わり。
叙情的な余談
以前の記事の1つへのコメントでは、機械による証拠の解釈がどのように発生するかについて質問されました。
知られているように、カリー-ハワード同型は証明とプログラム間の対応を決定します。 いくつかのアナロジーを構築できます：
したがって、Coqは用語のタイプを表示する単なる記号です。 ユーザーは、戦術を使用して出力アルゴリズムを変更できます。