proposition: Theorem compare : forall s1 s2 : t, Compare lt eq s1 s2.
proof: Proof. unfold lt, eq; induction s1 as [| c1 s1']. destruct s2; [apply EQ | apply LT]; auto. destruct s2 as [| c2 s2']; [apply GT; auto | ]. destruct (AsciiOT.compare c1 c2) as [? | ? | ?] eqn:Hcmp. apply LT; simpl; rewrite Hcmp; auto. unfold AsciiOT.eq in *; subst. destruct (IHs1' s2'); [apply LT | apply EQ | apply GT]; first [ simpl; rewrite Hcmp; assumption | subst; reflexivity ]. apply GT; simpl. destruct (AsciiOT.compare c2 c1) as [? | ? | ?] eqn:Hcmp'. reflexivity. unfold AsciiOT.eq in *; subst; not_ascii_lt_refl. do_ascii_lt_trans; not_ascii_lt_refl. Qed.
imports: OrderedType Bool Ascii NArith Coq.Strings.String