Coqでリストのreverse関数を書いてください。2回reverseすると元に戻る性質を証明してください。
- User
Coqでリストのreverse関数を書いてください。2回reverseすると元に戻る性質を証明してください。
Assistant
Coqでリストの
reverse関数を定義し、2回reverseすると元に戻る性質を証明するには、以下の手順で進めます。1. リストの定義
まず、リストをCoqで定義します。ここでは、単純な再帰的なリストを使用します。
Inductive list (A : Type) : Type := | nil : list A | cons : A -> list A -> list A. Notation "[]" := nil. Notation "[ x , .. , y ]" := (cons x .. (cons y nil) ..).2.
reverse関数の定義次に、リストを逆順にする
reverse関数を定義します。Fixpoint reverse {A : Type} (l : list A) : list A := match l with | [] => [] | cons x xs => reverse xs ++ [x] end.ここで、
++はリストの連結演算子です。Coqの標準ライブラリに定義されていますが、必要であれば自分で定義することもできます。Fixpoint app {A : Type} (l1 l2 : list A) : list A := match l1 with | [] => l2 | cons x xs => cons x (app xs l2) end. Notation "l1 ++ l2" := (app l1 l2).3. 2回
reverseすると元に戻る性質の証明最後に、2回
reverseすると元のリストに戻る性質を証明します。Lemma reverse_involutive : forall (A : Type) (l : list A), reverse (reverse l) = l. Proof. intros A l. induction l as [| x xs IH]. - (* l = [] *) reflexivity. - (* l = x :: xs *) simpl. rewrite IH. rewrite <- app_comm. reflexivity. Qed.説明
-
誘導: リスト
lに対して誘導法を使用します。- 基本ケース:
l = []の場合、reverse [] = []なので、reverse (reverse []) = []も成り立ちます。 - 誘導ステップ:
l = x :: xsの場合、reverse (x :: xs) = reverse xs ++ [x]となります。誘導仮定より、reverse (reverse xs) = xsなので、reverse (reverse (x :: xs)) = reverse ([x] ++ reverse xs) = reverse (reverse xs) ++ [x] = xs ++ [x] = x :: xsとなります。
- 基本ケース:
-
リストの連結の可換性:
app_commは、リストの連結が可換であることを示す補題です。つまり、[x] ++ xs = xs ++ [x]が成り立ちます。
これで、2回
reverseすると元に戻る性質が証明されました。補足:
app_commの証明app_commは、リストの連結が可換であることを示す補題です。以下にその証明を示します。Lemma app_comm : forall (A : Type) (x : A) (xs ys : list A), [x] ++ ys = ys ++ [x] -> xs ++ [x] = [x] ++ xs. Proof. intros A x xs ys. induction xs as [| y zs IH]. - (* xs = [] *) reflexivity. - (* xs = y :: zs *) simpl. rewrite IH. reflexivity. Qed. Lemma app_comm_single : forall (A : Type) (x : A) (ys : list A), [x] ++ ys = ys ++ [x]. Proof. intros A x ys. induction ys as [| y zs IH]. - (* ys = [] *) simpl. reflexivity. - (* ys = y :: zs *) simpl. rewrite IH. reflexivity. Qed.app_comm_singleは、単一要素のリストと任意のリストの連結が可換であることを示しています。これを利用して、app_commを証明できます。以上で、Coqでリストの
reverse関数を定義し、2回reverseすると元に戻る性質を証明しました。-
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 →
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 →
llama-4-maverick-17b-128e-instructCompare side by side →
claude-opus-4-20250514Compare side by side →