Skip to content
TheChatArchiveThe Chat Archive
Coherecommand-a-03-2025· CohereHugging 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. Cohere Assistant

    Coqでリストのreverse関数を定義し、2回reverseすると元に戻る性質を証明するには、以下の手順で進めます。

    1. リストの定義

    まず、リストをCoqで定義します。ここでは、単純な再帰的なリストを使用します。

    Inductive list (A : Type) : Type :=
      | nil : list A
      | cons : A -> list A -> list A.
    
    Notation "[]" := nil.
    Notation "[ x , .. , y ]" := (cons x .. (cons y nil) ..).
    

    2. reverse関数の定義

    次に、リストを逆順にするreverse関数を定義します。

    Fixpoint reverse {A : Type} (l : list A) : list A :=
      match l with
      | [] => []
      | cons x xs => reverse xs ++ [x]
      end.
    

    ここで、++はリストの連結演算子です。Coqの標準ライブラリに定義されていますが、必要であれば自分で定義することもできます。

    Fixpoint app {A : Type} (l1 l2 : list A) : list A :=
      match l1 with
      | [] => l2
      | cons x xs => cons x (app xs l2)
      end.
    
    Notation "l1 ++ l2" := (app l1 l2).
    

    3. 2回reverseすると元に戻る性質の証明

    最後に、2回reverseすると元のリストに戻る性質を証明します。

    Lemma reverse_involutive : forall (A : Type) (l : list A),
      reverse (reverse l) = l.
    Proof.
      intros A l.
      induction l as [| x xs IH].
      - (* l = [] *)
        reflexivity.
      - (* l = x :: xs *)
        simpl.
        rewrite IH.
        rewrite <- app_comm.
        reflexivity.
    Qed.
    

    説明

    • 誘導: リストlに対して誘導法を使用します。

      • 基本ケース: l = []の場合、reverse [] = []なので、reverse (reverse []) = []も成り立ちます。
      • 誘導ステップ: l = x :: xsの場合、reverse (x :: xs) = reverse xs ++ [x]となります。誘導仮定より、reverse (reverse xs) = xsなので、reverse (reverse (x :: xs)) = reverse ([x] ++ reverse xs) = reverse (reverse xs) ++ [x] = xs ++ [x] = x :: xsとなります。
    • リストの連結の可換性: app_commは、リストの連結が可換であることを示す補題です。つまり、[x] ++ xs = xs ++ [x]が成り立ちます。

    これで、2回reverseすると元に戻る性質が証明されました。

    補足: app_commの証明

    app_commは、リストの連結が可換であることを示す補題です。以下にその証明を示します。

    Lemma app_comm : forall (A : Type) (x : A) (xs ys : list A),
      [x] ++ ys = ys ++ [x] -> xs ++ [x] = [x] ++ xs.
    Proof.
      intros A x xs ys.
      induction xs as [| y zs IH].
      - (* xs = [] *)
        reflexivity.
      - (* xs = y :: zs *)
        simpl.
        rewrite IH.
        reflexivity.
    Qed.
    
    Lemma app_comm_single : forall (A : Type) (x : A) (ys : list A),
      [x] ++ ys = ys ++ [x].
    Proof.
      intros A x ys.
      induction ys as [| y zs IH].
      - (* ys = [] *)
        simpl.
        reflexivity.
      - (* ys = y :: zs *)
        simpl.
        rewrite IH.
        reflexivity.
    Qed.
    

    app_comm_singleは、単一要素のリストと任意のリストの連結が可換であることを示しています。これを利用して、app_commを証明できます。

    以上で、Coqでリストのreverse関数を定義し、2回reverseすると元に戻る性質を証明しました。

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