Skip to content
TheChatArchiveThe Chat Archive
Claudeclaude-sonnet-4-20250514· AnthropicHugging 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 Googlegemma-3-27b-it’s answer.
  1. User

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

  2. Claude Assistant

    Coqでリストのreverse関数と、2回reverseすると元に戻る性質の証明を書きます。

    Require Import List.
    Import ListNotations.
    
    (* リストのreverse関数を定義 *)
    Fixpoint reverse {A : Type} (l : list A) : list A :=
      match l with
      | [] => []
      | x :: xs => reverse xs ++ [x]
      end.
    
    (* 補助定理: reverseとappendの関係 *)
    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 xs IH].
      - simpl. rewrite app_nil_r. reflexivity.
      - simpl. rewrite IH. rewrite app_assoc. reflexivity.
    Qed.
    
    (* 補助定理: 単一要素のリストのreverse *)
    Lemma reverse_singleton : forall {A : Type} (x : A),
      reverse [x] = [x].
    Proof.
      intros A x.
      simpl. reflexivity.
    Qed.
    
    (* メインの定理: 2回reverseすると元に戻る *)
    Theorem reverse_involutive : forall {A : Type} (l : list A),
      reverse (reverse l) = l.
    Proof.
      intros A l.
      induction l as [| x xs IH].
      - (* 空リストの場合 *)
        simpl. reflexivity.
      - (* x :: xs の場合 *)
        simpl.
        rewrite reverse_app.
        rewrite reverse_singleton.
        rewrite IH.
        reflexivity.
    Qed.
    

    この証明では以下の手順を踏んでいます:

    1. reverse関数の定義: 再帰的に定義し、各要素を末尾に追加していく方式です。

    2. 補助定理の証明:

      • reverse_app: リストの連結とreverseの関係を示します
      • reverse_singleton: 単一要素リストのreverseは自分自身であることを示します
    3. メインの定理: リストに対する帰納法を使って証明します

      • 空リストの場合は自明
      • x :: xsの場合は、補助定理と帰納法の仮定を使って証明

    この証明により、任意の型のリストに対してreverse (reverse l) = lが成り立つことが形式的に証明されます。

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