proposition: Theorem snd_split_map_eq : forall (A B C : Set)(ls : list A)(f : A -> B * C), snd (split (map f ls)) = map (fun p => snd (f p)) ls.
proof: Proof. induction ls; intuition; simpl in *. remember (f a) as z. destruct z. remember (split (map f ls)) as z. destruct z. simpl. f_equal. assert (l0 = snd (l, l0)). trivial. rewrite H. rewrite Heqz0. eapply IHls. Qed.
imports: FCF.Rat List Permutation Arith FCF.EqDec FCF.StdNat Bool Permutation