Coqでリストのreverse関数を書いてください。2回reverseすると元に戻る性質を証明してください。
- User
Coqでリストのreverse関数を書いてください。2回reverseすると元に戻る性質を証明してください。
Assistant
Coqでリストの
reverse関数を定義し、その性質を証明する例を示します。まず、
reverse関数を定義します。Fixpoint reverse {A : Type} (l : list A) : list A := match l with | nil => nil | h :: t => reverse t ++ [h] end.次に、
reverse関数を2回適用すると元のリストに戻ることを証明します。そのためには、いくつかの補助的な補題が必要です。Lemma reverse_nil : forall {A : Type}, @reverse A nil = nil. Proof. reflexivity. Qed. Lemma reverse_cons : forall {A : Type} (x : A) (l : list A), reverse (x :: l) = reverse l ++ [x]. Proof. intros A x l. simpl. reflexivity. Qed. Lemma reverse_app : forall {A : Type} (l1 l2 : list A), reverse (l1 ++ l2) = reverse l2 ++ reverse l1. Proof. intros A l1 l2. induction l1 as [| x l1 IHl1]. - simpl. rewrite app_nil_r. reflexivity. - simpl. rewrite IHl1. rewrite app_assoc. reflexivity. Qed. Lemma reverse_involutive : forall {A : Type} (l : list A), reverse (reverse l) = l. Proof. intros A l. induction l as [| x l IHl]. - simpl. apply reverse_nil. - simpl. rewrite reverse_app. simpl. rewrite IHl. reflexivity. Qed.ここで証明した
reverse_involutive補題が、リストにreverseを2回適用すると元のリストに戻ることを示しています。これらの証明は、Coqの
tacticsを用いて行われます。reflexivityは、両辺が同じ形をしていることを示すために用いられ、inductionは、リストに関する性質を帰納的に証明するために用いられます。この例では、
reverse関数の挙動を理解し、その上でreverseを2回適用した結果が元のリストと等しくなることを形式的に証明しています。Coqのような証明支援系を用いることで、プログラムの正しさを厳密に検証することができます。
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.
Identical first prompt
claude-sonnet-4-20250514Compare side by side →
qwen3-30b-a3bCompare side by side →
command-a-03-2025Compare side by side →
gemma-3-27b-itCompare side by side →
gemini-2.5-flash-preview-04-17Compare side by side →
- o3-2025-04-16Compare side by side →
gemma-3-27b-itCompare side by side →
claude-sonnet-4-20250514Compare side by side →
gemini-2.5-pro-preview-05-06Compare side by side →
claude-3-7-sonnet-20250219-thinking-32kCompare side by side →
claude-opus-4-20250514Compare side by side →