sorting - Coq string sort lemmas -

i have string sort function defined below , want prove lemma sort_str_list_same below. not coq expert, tried solve using induction, not solve it. please me solving it. thanks,

require import ascii. require import string.  notation "x :: l" := (cons x l) (at level 60, right associativity). notation "[ ]" := nil. notation "[ x , .. , y ]" := (cons x .. (cons y nil) ..).  fixpoint ble_nat (n m : nat) : bool :=   match n   | o => true   | s n' =>       match m       | o => false       | s m' => ble_nat n' m'       end   end.  definition ascii_eqb (a a': ascii) : bool := if ascii_dec a' true else false.   (** true if s1 <= s2; s1 before/same s2 in alphabetical order *) fixpoint str_le_gt_dec (s1 s2 : string.string)   : bool :=  match s1, s2   | emptystring, emptystring => true  | string b, string a' b' =>          if ascii_eqb a' str_le_gt_dec b b'         else if ble_nat (nat_of_ascii a) (nat_of_ascii a')          true else false  | string b, _ => false  | _, string a' b' => true  end.  fixpoint aux (s: string.string) (ls: list string.string)   : list string.string :=  match ls   | nil => s :: nil  | :: l' => if str_le_gt_dec s                s :: :: l'                else :: (aux s l')  end.   fixpoint sort (ls: list string.string) : list string.string :=  match ls   | nil => nil  | :: tl => aux (sort tl)  end.   notation "s1 +s+ s2" := (string.append s1 s2) (at level 60, right associativity) : string_scope.  lemma sort_str_list_same: forall z1 z2 zm,   sort (z1 :: z2 :: zm) =  sort (z2 :: z1 :: zm). proof o.  admitted.  

your lemma equivalent forall z1 z2 zm, aux z1 (aux z2 zm) = aux z2 (aux z1 zm). here's how can prove similar theorem, arbitrary type order relation. use in case, have prove given hypothesis. note coq standard library defines sorting functions , proves lemmas them, may able solve problem without having prove many things.

require import coq.lists.list.  section sort.  variable : type.  variable comp : -> -> bool.  hypothesis comp_trans :   forall b c, comp b = true ->                 comp b c = true ->                 comp c = true.  hypothesis comp_antisym :   forall b, comp b = true ->               comp b = true ->               = b.  hypothesis comp_total :   forall b, comp b = true \/ comp b = true.  fixpoint insert (a : a) (l : list a) : list :=   match l     | nil => :: nil     | a' :: l' => if comp a' :: a' :: l'                   else a' :: insert l'   end.  lemma l1 : forall a1 a2 l, insert a1 (insert a2 l) = insert a2 (insert a1 l). proof.   intros a1 a2 l.   induction l [|a l ih]; simpl.   - destruct (comp a1 a2) eqn:e1.     + destruct (comp a2 a1) eqn:e2; trivial.       rewrite (comp_antisym _ _ e1 e2). trivial.     + destruct (comp a2 a1) eqn:e2; trivial.       destruct (comp_total a1 a2); congruence.   - destruct (comp a2 a) eqn:e1; simpl;     destruct (comp a1 a) eqn:e2; simpl;     destruct (comp a1 a2) eqn:e3; simpl;     destruct (comp a2 a1) eqn:e4; simpl;     try rewrite e1; trivial;     try solve [rewrite (comp_antisym _ _ e3 e4) in *; congruence];     try solve [destruct (comp_total a1 a2); congruence].     + assert (h := comp_trans _ _ _ e3 e1). congruence.     + assert (h := comp_trans _ _ _ e4 e2). congruence. qed.  section sort.