Skip to content
TheChatArchiveThe Chat Archive
Metallama-4-maverick-17b-128e-instruct· MetaHugging 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-opus-4-20250514’s answer.
  1. User

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

  2. Meta Assistant

    Coqでリストのreverse関数を定義し、その性質を証明する例を示します。

    まず、reverse関数を定義します。

    Fixpoint reverse {A : Type} (l : list A) : list A :=
      match l with
      | nil => nil
      | h :: t => reverse t ++ [h]
      end.
    

    次に、reverse関数を2回適用すると元のリストに戻ることを証明します。そのためには、いくつかの補助的な補題が必要です。

    Lemma reverse_nil : forall {A : Type}, @reverse A nil = nil.
    Proof.
      reflexivity.
    Qed.
    
    Lemma reverse_cons : forall {A : Type} (x : A) (l : list A),
      reverse (x :: l) = reverse l ++ [x].
    Proof.
      intros A x l.
      simpl.
      reflexivity.
    Qed.
    
    Lemma reverse_app : forall {A : Type} (l1 l2 : list A),
      reverse (l1 ++ l2) = reverse l2 ++ reverse l1.
    Proof.
      intros A l1 l2.
      induction l1 as [| x l1 IHl1].
      - simpl. rewrite app_nil_r. reflexivity.
      - simpl. rewrite IHl1. rewrite app_assoc. reflexivity.
    Qed.
    
    Lemma reverse_involutive : forall {A : Type} (l : list A),
      reverse (reverse l) = l.
    Proof.
      intros A l.
      induction l as [| x l IHl].
      - simpl. apply reverse_nil.
      - simpl. rewrite reverse_app. simpl. rewrite IHl. reflexivity.
    Qed.
    

    ここで証明したreverse_involutive補題が、リストにreverseを2回適用すると元のリストに戻ることを示しています。

    これらの証明は、Coqのtacticsを用いて行われます。reflexivityは、両辺が同じ形をしていることを示すために用いられ、inductionは、リストに関する性質を帰納的に証明するために用いられます。

    この例では、reverse関数の挙動を理解し、その上でreverseを2回適用した結果が元のリストと等しくなることを形式的に証明しています。Coqのような証明支援系を用いることで、プログラムの正しさを厳密に検証することができます。

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