fact: Fixpoint merge_msets l1 := match l1 with | nil (h1,n1) => fun l2 => insert n1 h1 l2 | (h1,n1)::t1 => let fix merge_aux l2 := match l2 with | nil (h2,n2) => match compare h1 h2 with | Eq => (h1,Pplus n1 n2) :: t1 | Lt => (h1,n1):: merge_msets t1 l2 | Gt => (h2,n2):: l1 end | (h2,n2)::t2 => match compare h1 h2 with | Eq => (h1,Pplus n1 n2)::merge_msets t1 t2 | Lt => (h1,n1)::merge_msets t1 l2 | Gt => (h2,n2)::merge_aux t2 end end in merge_aux end.
imports: Coq(Arith NArith List RelationClasses)