Skip to content

Instantly share code, notes, and snippets.

@mbrcknl
Created January 29, 2015 23:35
Show Gist options
  • Save mbrcknl/bfaa72c2ec6ff32a2826 to your computer and use it in GitHub Desktop.
Save mbrcknl/bfaa72c2ec6ff32a2826 to your computer and use it in GitHub Desktop.
Require Import List.
Import ListNotations.
Set Implicit Arguments.
Fixpoint reverse (X: Type) (xs: list X): list X :=
match xs with
| [] => []
| x :: xs' => reverse xs' ++ [x]
end.
Lemma app_eq_nil: forall (X: Type) (xs ys: list X), xs ++ ys = xs -> ys = [].
induction xs; simpl; inversion 1; auto.
Qed.
Theorem rev_spec_complete:
forall (X: Type) (rev: list X -> list X),
(forall x, rev [x] = [x]) ->
(forall xs ys, rev (xs ++ ys) = rev ys ++ rev xs) ->
(forall xs, rev xs = reverse xs).
Proof.
intros X rev S A; induction xs as [|x' xs']; simpl.
assert (rev ([] ++ []) = rev [] ++ rev []) as H; auto.
apply (@app_eq_nil X (rev [])); symmetry; apply H.
assert (x' :: xs' = [x'] ++ xs') as H; auto.
rewrite H; rewrite <- IHxs'; rewrite A; rewrite S; reflexivity.
Qed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment