Skip to content
TheChatArchiveThe Chat Archive
Geminigemini-2.5-pro-preview-05-06· 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 Claudeclaude-3-7-sonnet-20250219-thinking-32k’s answer.
  1. User

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

  2. Gemini 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 を証明するために、いくつか補助定理が必要になります。

    1. 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.
    
    1. 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.
    

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