proposition: Lemma merge_equiv : forall m m', merge' m m' = merge m m'.
proof: Proof. unfold merge'. induction m as [|(k,e) m IHm]; intros. - simpl. induction m' as [|(k',e') m' IHm']; simpl; rewrite ?IHm'; auto. - induction m' as [|(k',e') m' IHm']; simpl. + f_equal. clear k e IHm. induction m as [|(k,e) m IHm]; simpl; rewrite ?IHm; auto. + elim X.compare_spec; intros; simpl; f_equal. * apply IHm. * apply IHm. * apply IHm'. Qed.
imports: Coq(OrdersFacts OrdersLists)