Skip to content
TheChatArchiveThe Chat Archive
Geminigemini-2.5-flash-preview-04-17· GoogleHugging Face LMArena Human Preference 140K

Coqでリストのreverse関数を書いてください。2回reverseすると元に戻る性質を証明してください。

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with o3-2025-04-16’s answer.
  1. User

    Coqでリストのreverse関数を書いてください。2回reverseすると元に戻る性質を証明してください。

  2. Gemini Assistant

    はい、承知いたしました。Coqでリストのreverse関数を定義し、reverseを2回適用すると元のリストに戻るという性質を証明します。

    Coqの標準ライブラリのListモジュールを使用します。

    Require Import Coq.List.List.
    Import ListNotations. (* []や[1;2;3]のような記法を使えるようにします *)
    
    (*
    リストの反転関数を定義します。
    アキュムレータを使った効率的な定義を使用します。
    reverse_acc acc l は、l を反転したものを acc の先頭に追加したリストを返します。
    *)
    Fixpoint reverse_acc {A : Type} (acc : list A) (l : list A) : list A :=
      match l with
      | nil => acc (* l が空なら、反転した要素はもうないので acc を返す *)
      | x :: tl => reverse_acc (x :: acc) tl (* l の先頭 x を acc の先頭に追加し、残りの tl を再帰的に処理 *)
      end.
    
    Definition reverse {A : Type} (l : list A) : list A :=
      reverse_acc nil l. (* reverse は空のアキュムレータから始める *)
    
    (*
    例: reverse [1; 2; 3]
    -> reverse_acc nil [1; 2; 3]
    -> reverse_acc (1 :: nil) [2; 3] = reverse_acc [1] [2; 3]
    -> reverse_acc (2 :: [1]) [3] = reverse_acc [2; 1] [3]
    -> reverse_acc (3 :: [2; 1]) nil = reverse_acc [3; 2; 1] nil
    -> [3; 2; 1]
    *)
    
    (* --- 証明に必要な補題(Lemma) --- *)
    
    (* 補題1: reverse_acc の性質 *)
    (* reverse_acc acc l は、reverse l と acc を結合したものに等しい。 *)
    (* つまり reverse_acc acc l = (reverse l) ++ acc *)
    (* 証明は l に関する帰納法で行います。 *)
    Lemma reverse_acc_eq_app_reverse : forall {A : Type} (acc l : list A),
      reverse_acc acc l = (reverse l) ++ acc.
    Proof.
      intros A acc l.
      induction l as [| x tl IH].
      (* l = nil の場合 *)
      simpl. (* reverse_acc acc nil は acc に、reverse nil は nil に簡約されます *)
      reflexivity. (* acc = nil ++ acc は自明です (app_nil_r) *)
    
      (* l = x :: tl の場合 *)
      simpl. (* reverse_acc acc (x :: tl) は reverse_acc (x :: acc) tl に簡約されます *)
      (* 目標: reverse_acc (x :: acc) tl = reverse (x :: tl) ++ acc *)
      (* 帰納法の仮説 IH は reverse_acc acc tl = reverse tl ++ acc です。
         これを acc := x :: acc として適用します。 *)
      rewrite IH with (acc := x :: acc).
      (* 目標: reverse tl ++ (x :: acc) = reverse (x :: tl) ++ acc *)
      (* reverse (x :: tl) を展開・簡約します *)
      unfold reverse. simpl. (* reverse (x :: tl) は reverse_acc nil (x :: tl) を経て reverse_acc [x] tl になります *)
      (* 目標: reverse tl ++ (x :: acc) = reverse_acc [x] tl ++ acc *)
      (* reverse_acc [x] tl に対して、示したい補題 (reverse_acc acc l = reverse l ++ acc) を適用します。
         ここで acc := [x], l := tl です。 *)
      rewrite reverse_acc_eq_app_reverse with (acc := [x]) (l := tl).
      (* 目標: reverse tl ++ (x :: acc) = (reverse tl ++ [x]) ++ acc *)
      (* x :: acc は [x] ++ acc と等しいです *)
      (* 目標は reverse tl ++ ([x] ++ acc) = (reverse tl ++ [x]) ++ acc となります *)
      (* これはリスト結合 ++ の結合則 (app_assoc) により成り立ちます *)
      rewrite app_assoc.
      reflexivity.
    Qed.
    
    (* 補題2: 要素が1つのリストの reverse はそのリスト自身 *)
    Lemma reverse_singleton : forall {A : Type} (x : A),
      reverse [x] = [x].
    Proof.
      intros A x.
      unfold reverse. simpl. (* reverse [x] -> reverse_acc nil [x] -> reverse_acc (x::nil) nil *)
      reflexivity. (* reverse_acc (x::nil) nil は x::nil、つまり [x] に簡約されます *)
    Qed.
    
    (* 補題3: reverse はリスト結合 ++ に対して分配的である (順序は反転する) *)
    (* reverse (a ++ b) = (reverse b) ++ (reverse a) *)
    (* 証明は a に関する帰納法で行います。 *)
    Lemma reverse_app : forall {A : Type} (a b : list A),
      reverse (a ++ b) = (reverse b) ++ (reverse a).
    Proof.
      intros A a b.
      induction a as [| x a' IH].
      (* a = nil の場合 *)
      simpl. (* reverse (nil ++ b) は reverse b に、reverse nil は nil に簡約されます *)
      reflexivity. (* reverse b = reverse b ++ nil は自明です (app_nil_r) *)
    
      (* a = x :: a' の場合 *)
      simpl. (* reverse ((x :: a') ++ b) は reverse (x :: (a' ++ b)) に簡約されます *)
      (* 目標: reverse (x :: (a' ++ b)) = reverse b ++ reverse (x :: a') *)
      unfold reverse. simpl. (* reverse (x :: ...) は reverse_acc [x] ... に簡約されます *)
      (* 目標: reverse_acc [x] (a' ++ b) = reverse b ++ reverse (x :: a') *)
      (* reverse_acc [x] (a' ++ b) に対して、補題1 (reverse_acc_eq_app_reverse) を acc:=[x], l:=(a' ++ b) として適用します *)
      rewrite reverse_acc_eq_app_reverse with (acc := [x]) (l := a' ++ b).
      (* 目標: reverse (a' ++ b) ++ [x] = reverse b ++ reverse (x :: a') *)
      (* 帰納法の仮説 IH は reverse (a' ++ b) = reverse b ++ reverse a' です *)
      rewrite IH.
      (* 目標: (reverse b ++ reverse a') ++ [x] = reverse b ++ reverse (x :: a') *)
      (* 右辺の reverse (x :: a') を展開・簡約します *)
      unfold reverse. simpl. (* reverse (x :: a') は reverse_acc [x] a' になります *)
      (* 目標: (reverse b ++ reverse a') ++ [x] = reverse b ++ reverse_acc [x] a' *)
      (* reverse_acc [x] a' に対して、補題1 (reverse_acc_eq_app_reverse) を acc:=[x], l:=a' として適用します *)
      rewrite reverse_acc_eq_app_reverse with (acc := [x]) (l := a').
      (* 目標: (reverse b ++ reverse a') ++ [x] = reverse b ++ (reverse a' ++ [x]) *)
      (* これはリスト結合 ++ の結合則 (app_assoc) により成り立ちます *)
      rewrite <- app_assoc. (* 結合順を右辺に合わせるために <- を使います *)
      reflexivity.
    Qed.
    
    
    (* --- 主定理 --- *)
    
    (* 定理: reverse を2回適用すると元のリストに戻る *)
    Theorem reverse_reverse : forall {A : Type} (l : list A),
      reverse (reverse l) = l.
    Proof.
      intros A l.
      induction l as [| x tl IH].
      (* l = nil の場合 *)
      simpl. (* reverse (reverse nil) は reverse nil に簡約されます *)
      simpl. (* reverse nil は nil に簡約されます *)
      reflexivity. (* nil = nil は自明です *)
    
      (* l = x :: tl の場合 *)
      simpl. (* reverse (reverse (x :: tl)) *)
      (* 目標: reverse (reverse (x :: tl)) = x :: tl *)
      (* reverse (x :: tl) を展開・簡約します *)
      unfold reverse. simpl. (* reverse (x :: tl) は reverse_acc [x] tl になります *)
      (* 目標: reverse (reverse_acc [x] tl) = x :: tl *)
      (* reverse_acc [x] tl に対して、補題1 (reverse_acc_eq_app_reverse) を acc:=[x], l:=tl として適用します *)
      rewrite reverse_acc_eq_app_reverse with (acc := [x]) (l := tl).
      (* 目標: reverse (reverse tl ++ [x]) = x :: tl *)
      (* reverse (reverse tl ++ [x]) に対して、補題3 (reverse_app) を a:=(reverse tl), b:=[x] として適用します *)
      rewrite reverse_app with (a := reverse tl) (b := [x]).
      (* 目標: reverse [x] ++ reverse (reverse tl) = x :: tl *)
      (* reverse [x] に対して、補題2 (reverse_singleton) を適用します *)
      rewrite reverse_singleton.
      (* 目標: [x] ++ reverse (reverse tl) = x :: tl *)
      (* 帰納法の仮説 IH は reverse (reverse tl) = tl です *)
      rewrite IH.
      (* 目標: [x] ++ tl = x :: tl *)
      (* [x] ++ tl は x :: nil ++ tl であり、nil ++ tl は tl なので、x :: tl に簡約されます *)
      simpl.
      reflexivity.
    Qed.
    

    解説:

    1. Require Import Coq.List.List.: Coqの標準リストライブラリをインポートします。
    2. Import ListNotations.: [1; 2; 3] のような便利なリスト記法を有効にします。
    3. reverse_acc: アキュムレータaccを使ってリストlを反転するヘルパー関数です。再帰の各ステップで、lの先頭要素をaccの先頭に追加していきます。これにより、lの要素が逆順にaccに積み重ねられていきます。
    4. reverse: reverse_accを空のアキュムレータnilで呼び出すことで、リスト全体を反転します。
    5. Lemma reverse_acc_eq_app_reverse: reverse_acc acc l が (reverse l) ++ acc に等しいことを示す補題です。これはアキュムレータを使った反転関数の重要な性質であり、他の補題や主定理の証明で鍵となります。リストlに関する帰納法で証明します。証明中では、この補題自身やリスト結合の結合則(app_assoc)を使用しています。
    6. Lemma reverse_singleton: 1つの要素xを持つリスト[x]をreverseすると、元のリスト[x]のままになることを示します。これは自明なようでいて、定義に基づくと計算が必要です。
    7. Lemma reverse_app: reverse (a ++ b) = (reverse b) ++ (reverse a) という、reverseがリスト結合(++)に対して分配的である(ただし左右が入れ替わる)ことを示す標準的な補題です。リストaに関する帰納法で証明し、その中でreverse_acc_eq_app_reverseやapp_assocを使用します。
    8. Theorem reverse_reverse: これが最終的に証明したい定理です。任意のリストlに対してreverse (reverse l) = l が成り立つことを示します。リストlに関する帰納法で証明します。帰納ステップでは、reverse (x :: tl) を展開し、補題1 (reverse_acc_eq_app_reverse)、補題3 (reverse_app)、補題2 (reverse_singleton)、そして帰納法の仮説 (IH: reverse (reverse tl) = tl) を順次適用することで証明が完了します。

    このCoqコードをCoqIDEなどで実行すると、DefinitionやLemma、TheoremがSuccessfully defined/provedされたことを確認できます。

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.