proposition: Lemma Permutation_KeyBasedPartition : forall key m bst_m b, Permutation (fold (fun (_ : XMap.Raw.key) (trie : Trie) (a : list BagType) => Trie_enumerate trie ++ a) m b) (XMap.fold (fun (_ : XMap.key) (trie : Trie) (a : list BagType) => Trie_enumerate trie ++ a) (fst (partition (KeyBasedPartitioningFunction Trie key) {| XMap.this := m; XMap.is_bst := bst_m |})) (XMap.fold (fun (_ : XMap.key) (trie : Trie) (a : list BagType) => Trie_enumerate trie ++ a) (snd (partition (KeyBasedPartitioningFunction Trie key) {| XMap.this := m; XMap.is_bst := bst_m |})) b)) .
proof: Proof. intros. pose proof (partition_Partition_simple _ (KeyBasedPartitioningFunction Trie key0) (KeyBasedPartitioningFunction_Proper _ _) (XMap.Bst bst_m)) as part. erewrite Partition_fold with (f := (fun (_ : key) (trie : Trie) (a : list BagType) => Trie_enumerate trie ++ a)) (m := {| XMap.this := m; XMap.is_bst := bst_m |} ) (i := b); (eauto using part, Permutation_Equivalence, Tries_enumerate_app_Proper, Tries_enumerate_app_transpose_neqkey). Qed.
imports: Fiat.Common.Coq__8_4__8_5__Compat Fiat.QueryStructure.Implementation.DataStructures.Bags.BagsInterface Fiat.QueryStructure.Implementation.DataStructures.Bags.BagsProperties Coq.FSets.FMapInterface Coq.FSets.FMapFacts Coq.FSets.FMapAVL Coq.ZArith.ZArith Fiat.Common Fiat.Common.List.ListFacts Fiat.Common.List.FlattenList Fiat.Common.SetEqProperties Fiat.Common.FMapExtensions Fiat.Common.List.PermutationFacts Fiat.QueryStructure.Specification.SearchTerms.ListPrefix