0

やらなければならないタスクがありますが、それを行う方法がわかりません：

reverse, rev :: [a] [a]

reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

rev = aux [] where
    aux ys [] = ys
    aux ys (x:xs) = aux (x:ys) xs

「それを証明してください:reverse=rev」

あなたの助けをいただければ幸いです。ありがとうございました。

PS。いくつかの例を使用してそれを行うことができますが、それは専門的ではないと思います

4

4 に答える 4

3

構造的帰納法によってずさんな証明を作成することはできますが、底を正しく処理する証明が必要な場合は、それほど簡単ではありません。

于 2011-05-08T18:23:47.977 に答える
2

誘導。ベースケースは簡単です。誘導ステップは、あまり難しくないはずです。

于 2011-05-08T17:36:37.413 に答える
1

等価性を直接証明しようとする代わりに、関数ごとに (帰納法を使用して) 実際にリストを逆にすることを証明します。両方ともリストを逆にする場合、それらは同等です。

証明スケッチ:

rev がすべてのリストで機能することを証明したいと思います。

長さ 0 の 基本ケースリスト: rev [] が正しく計算されることを証明する

帰納的な場合: 任意の n について、rev が n-1 までの長さのリストを反転できると仮定して、rev が長さ n の任意のリストを反転できることを証明する

于 2011-05-08T18:10:47.453 に答える
1

リスト反転関数は、有限リストが与えられた場合にのみ出力を生成できるため、このコードを Coq (リストは常に有限) に変換し、そこで目的のステートメントを証明できます (下を無視します)。

この証明は私自身のものではありません。標準ライブラリの証明を少し修正したものです。

Open Scope list_scope.

Require List.
Require Import FunctionalExtensionality.

Section equivalence.

  Variable A : Type.

  (* The reverse function is already defined in the standard library as List.rev. *)
  Notation reverse := (@List.rev A).

  Fixpoint aux (ys l2 : list A) :=
    match l2 with
      nil => ys
      | x :: xs => aux (x :: ys) xs
    end.

  Definition rev : list A -> list A
    := aux nil.

  Lemma aux_rev : forall l l', aux l' l = reverse l ++ l'.
  Proof.
    induction l; simpl; auto; intros.
    rewrite <- List.app_assoc; firstorder.
  Qed.

  Theorem both_equal : reverse = rev.
    extensionality xs.
    unfold rev.
    rewrite aux_rev.
    now rewrite List.app_nil_r.
  Qed.

End equivalence.
于 2011-05-08T19:14:56.080 に答える