Coqでリストのreverse関数を書いてください。2回reverseすると元に戻る性質を証明してください。
- User
Coqでリストのreverse関数を書いてください。2回reverseすると元に戻る性質を証明してください。
Assistant
はい、Coqでリストの
reverse関数を定義し、reverse (reverse l) = lという性質を証明します。 一般的にreverseは、アキュムレータを使った末尾再帰の補助関数を使って定義すると効率的です。まず、必要なライブラリをインポートします。
Require Import List. Import ListNotations. Open Scope list_scope.次に、
reverse関数を定義します。 アキュムレータaccを持つ補助関数reverse_auxをまず定義します。reverse_aux acc lはlを反転してaccの前に連結したものを返します。reverse lはreverse_aux nil lとして定義されます。Fixpoint reverse_aux {A : Type} (acc : list A) (l : list A) : list A := match l with | nil => acc | x :: xs => reverse_aux (x :: acc) xs end. Definition reverse {A : Type} (l : list A) : list A := reverse_aux nil l.いくつか簡単な例で試してみましょう。
Example rev_ex1 : reverse (1 :: 2 :: 3 :: nil) = 3 :: 2 :: 1 :: nil. Proof. reflexivity. Qed. Example rev_ex2 : reverse nil = (nil : list nat). Proof. reflexivity. Qed. Example rev_ex3 : reverse (reverse (1 :: 2 :: nil)) = 1 :: 2 :: nil. Proof. reflexivity. Qed.reverse (reverse l) = lを証明するために、いくつか補助定理が必要になります。reverse_aux acc l = (reverse l) ++ accこれは、アキュムレータ付きの補助関数が、メインのreverse関数とリストの連結(++)でどのように関連しているかを示します。 便宜上、reverse lをrev lと書くことにします。
Lemma reverse_aux_app_spec : forall A (acc l : list A), reverse_aux acc l = (reverse l) ++ acc. Proof. intros A acc l. induction l as [| x xs IHxs]. - (* Case nil *) simpl. (* reverse_aux acc nil = acc *) (* (reverse nil) ++ acc = (reverse_aux nil nil) ++ acc = nil ++ acc = acc *) reflexivity. - (* Case x :: xs *) simpl. (* reverse_aux acc (x :: xs) = reverse_aux (x :: acc) xs *) (* (reverse (x :: xs)) ++ acc = (reverse_aux nil (x :: xs)) ++ acc *) (* = (reverse_aux (x :: nil) xs) ++ acc *) rewrite IHxs. (* reverse_aux (x :: acc) xs = (reverse xs) ++ (x :: acc) *) assert (H_rev_xs_cons : reverse (x :: xs) = reverse_aux (x :: nil) xs). { simpl. reflexivity. } rewrite H_rev_xs_cons. rewrite (IHxs (x :: nil)). (* reverse_aux (x :: nil) xs = (reverse xs) ++ (x :: nil) *) (* Goal: (reverse xs) ++ (x :: acc) = ((reverse xs) ++ (x :: nil)) ++ acc *) rewrite List.app_assoc. (* Goal: (reverse xs) ++ (x :: acc) = (reverse xs) ++ ((x :: nil) ++ acc) *) (* We need to show x :: acc = (x :: nil) ++ acc *) f_equal. simpl. reflexivity. Qed.reverse (l1 ++ l2) = (reverse l2) ++ (reverse l1)これは、連結されたリストの反転が、各リストを反転して逆順に連結したものと等しいことを示します。
Lemma reverse_app_distr : forall A (l1 l2 : list A), reverse (l1 ++ l2) = (reverse l2) ++ (reverse l1). Proof. intros A l1 l2. induction l1 as [| x xs IHxs]. - (* Case nil *) simpl. (* reverse (nil ++ l2) = reverse l2 *) (* (reverse l2) ++ (reverse nil) = (reverse l2) ++ nil *) rewrite app_nil_r. reflexivity. - (* Case x :: xs *) simpl. (* reverse ((x :: xs) ++ l2) = reverse (x :: (xs ++ l2)) = reverse_aux (x :: nil) (xs ++ l2) *) (* (reverse l2) ++ (reverse (x :: xs)) = (reverse l2) ++ (reverse_aux (x :: nil) xs) *) (* LHS: reverse_aux (x :: nil) (xs ++ l2) *) (* Using reverse_aux_app_spec: reverse_aux (x :: nil) (xs ++ l2) = reverse (xs ++ l2) ++ (x :: nil) *) rewrite (reverse_aux_app_spec (x :: nil) (xs ++ l2)). (* Now LHS is: (reverse (xs ++ l2)) ++ (x :: nil) *) (* Using IHxs on (reverse (xs ++ l2)): (reverse l2 ++ reverse xs) ++ (x :: nil) *) rewrite IHxs. (* RHS: (reverse l2) ++ (reverse (x :: xs)) *) (* reverse (x :: xs) is reverse_aux (x :: nil) xs *) assert (H_rev_cons : reverse (x :: xs) = reverse_aux (x :: nil) xs). { simpl. reflexivity. } rewrite H_rev_cons. (* Now RHS is: (reverse l2) ++ (reverse_aux (x :: nil) xs) *) (* Using reverse_aux_app_spec on reverse_aux (x :: nil) xs: (reverse xs) ++ (x :: nil) *) rewrite (reverse_aux_app_spec (x :: nil) xs). (* Now RHS is: (reverse l2) ++ ((reverse xs) ++ (x :: nil)) *) (* Goal: ((reverse l2) ++ (reverse xs)) ++ (x :: nil) = (reverse l2) ++ ((reverse xs) ++ (x :: nil)) *) rewrite List.app_assoc. reflexivity. Qed.これらの補助定理を使って、メインの定理
reverse_involutiveを証明します。Theorem reverse_involutive : forall A (l : list A), reverse (reverse l) = l. Proof. intros A l. induction l as [| x xs IHxs]. - (* Case nil *) simpl. reflexivity. - (* Case x :: xs *) (* Goal: reverse (reverse (x :: xs)) = x :: xs *) (* LHS: reverse (reverse (x :: xs)) *) (* reverse (x :: xs) = reverse_aux (x :: nil) xs *) assert (H_rev_cons : reverse (x :: xs) = reverse_aux (x :: nil) xs). { simpl. reflexivity. } rewrite H_rev_cons. (* LHS is now: reverse (reverse_aux (x :: nil) xs) *) (* Use reverse_aux_app_spec: reverse_aux (x :: nil) xs = (reverse xs) ++ (x :: nil) *) rewrite (reverse_aux_app_spec (x :: nil) xs). (* LHS is now: reverse ((reverse xs) ++ (x :: nil)) *) (* Use reverse_app_distr: reverse (L1 ++ L2) = reverse L2 ++ reverse L1 *) (* Let L1 = reverse xs, L2 = x :: nil *) rewrite (reverse_app_distr (reverse xs) (x :: nil)). (* LHS is now: (reverse (x :: nil)) ++ (reverse (reverse xs)) *) (* Simplify reverse (x :: nil) *) assert (H_rev_single : reverse (x :: nil) = x :: nil). { simpl. reflexivity. } rewrite H_rev_single. (* LHS is now: (x :: nil) ++ (reverse (reverse xs)) *) (* Use IHxs: reverse (reverse xs) = xs *) rewrite IHxs. (* LHS is now: (x :: nil) ++ xs *) simpl. (* (x :: nil) ++ xs = x :: xs *) reflexivity. Qed.これで、
reverse関数とその性質の証明が完了しました。コード全体のまとめ:
Require Import List. Import ListNotations. Open Scope list_scope. (* Reverse function definition using an accumulator *) Fixpoint reverse_aux {A : Type} (acc : list A) (l : list A) : list A := match l with | nil => acc | x :: xs => reverse_aux (x :: acc) xs end. Definition reverse {A : Type} (l : list A) : list A := reverse_aux nil l. (* Examples *) Example rev_ex1 : reverse (1 :: 2 :: 3 :: nil) = 3 :: 2 :: 1 :: nil. Proof. reflexivity. Qed. Example rev_ex2 : reverse nil = (nil : list nat). Proof. reflexivity. Qed. Example rev_ex3 : reverse (reverse (1 :: 2 :: nil)) = 1 :: 2 :: nil. Proof. reflexivity. Qed. (* Lemma 1: reverse_aux acc l = (reverse l) ++ acc *) Lemma reverse_aux_app_spec : forall A (acc l : list A), reverse_aux acc l = (reverse l) ++ acc. Proof. intros A acc l. induction l as [| x xs IHxs]. - simpl. reflexivity. - simpl. rewrite IHxs. assert (H_rev_xs_cons : reverse (x :: xs) = reverse_aux (x :: nil) xs). { simpl. reflexivity. } rewrite H_rev_xs_cons. rewrite (IHxs (x :: nil)). rewrite List.app_assoc. f_equal. simpl. reflexivity. Qed. (* Lemma 2: reverse (l1 ++ l2) = (reverse l2) ++ (reverse l1) *) Lemma reverse_app_distr : forall A (l1 l2 : list A), reverse (l1 ++ l2) = (reverse l2) ++ (reverse l1). Proof. intros A l1 l2. induction l1 as [| x xs IHxs]. - simpl. rewrite app_nil_r. reflexivity. - simpl. rewrite (reverse_aux_app_spec (x :: nil) (xs ++ l2)). rewrite IHxs. assert (H_rev_cons : reverse (x :: xs) = reverse_aux (x :: nil) xs). { simpl. reflexivity. } rewrite H_rev_cons. rewrite (reverse_aux_app_spec (x :: nil) xs). rewrite List.app_assoc. reflexivity. Qed. (* Main Theorem: reverse (reverse l) = l *) Theorem reverse_involutive : forall A (l : list A), reverse (reverse l) = l. Proof. intros A l. induction l as [| x xs IHxs]. - simpl. reflexivity. - assert (H_rev_cons : reverse (x :: xs) = reverse_aux (x :: nil) xs). { simpl. reflexivity. } rewrite H_rev_cons. rewrite (reverse_aux_app_spec (x :: nil) xs). rewrite (reverse_app_distr (reverse xs) (x :: nil)). assert (H_rev_single : reverse (x :: nil) = x :: nil). { simpl. reflexivity. } rewrite H_rev_single. rewrite IHxs. simpl. reflexivity. Qed.
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 →
claude-3-7-sonnet-20250219-thinking-32kCompare side by side →
llama-4-maverick-17b-128e-instructCompare side by side →
claude-opus-4-20250514Compare side by side →