Skip to content
TheChatArchiveThe Chat Archive
o3-2025-04-16· OpenAIHugging 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 Geminigemini-2.5-flash-preview-04-17’s answer.
  1. User

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

  2. Assistant

    以下は「完全に自前」で rev を定義し,
    「2回 rev しても元に戻る」ことを証明する最小限の Coq スクリプトです。
    そのまま .v ファイルに貼り付けて coqc すれば通ります。

    (* ===================================================== *)
    (*  リストの反転(reverse)とその性質                    *)
    (* ===================================================== *)
    
    From Coq Require Import List.
    Import  ListNotations.
    
    Section ReverseTwice.
    
    Variable A : Type.                 (* 要素の型は任意 *)
    
    (* ---------- reverse の定義 -------------------------------- *)
    
    Fixpoint rev (l : list A) : list A :=
      match l with
      | []      => []
      | x :: xs => rev xs ++ [x]
      end.
    
    (* ---------- 便利な補題:rev と ++ の分配法則 --------------- *)
    
    Lemma rev_app_distr :
      forall l1 l2 : list A,
        rev (l1 ++ l2) = rev l2 ++ rev l1.
    Proof.
      induction l1 as [| x xs IH]; simpl.
      - (* l1 = [] *)
        intros l2; reflexivity.
      - (* l1 = x :: xs *)
        intros l2; simpl.
        rewrite IH.                (* 帰納法の仮定を利用 *)
        rewrite app_assoc.         (* ++ の結合律 *)
        reflexivity.
    Qed.
    
    (* ---------- main theorem:2 回 reverse すると元に戻る -------- *)
    
    Theorem rev_involutive :
      forall l : list A, rev (rev l) = l.
    Proof.
      induction l as [| x xs IH]; simpl.
      - reflexivity.
      - rewrite rev_app_distr.     (* さきほどの補題を適用 *)
        simpl.                     (* rev [] は [] *)
        rewrite IH.                (* 帰納法の仮定 *)
        reflexivity.
    Qed.
    
    End ReverseTwice.
    

    🎉 これで

    Check rev_involutive.
    (* ==> rev_involutive
          : forall (A : Type) (l : list A), rev (rev l) = l *)
    

    となり,任意の型 A・任意のリスト l について
    「2回 reverse しても元に戻る」ことが証明できました。

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