How to implement Data.Map.insertList*?
Mirko Rahn
rahn at ira.uka.de
Wed Feb 23 06:16:13 EST 2005
The old FiniteMap module contains the addListToFM* functions that are
missing in Data.Map. But how to implement it?
First answer:
insertList_foldl :: Ord k => [(k,a)] -> Map.Map k a -> Map.Map k a
insertList_foldl = flip (foldl ins) where fluc = flip . uncurry
ins = fluc Map.insert
Second answer:
insertList_union :: Ord k => [(k,a)] -> Map.Map k a -> Map.Map k a
insertList_union kas = Map.union (Map.fromList kas)
Situation and Problem:
We already have a map of size n and want to insert a list with m
elements. Then we look at the documentation and one gets:
* For the first answer we do need O(sum_{i=0}^{m-1}log(n+i)) =
O(log((m+n)!/n!)) operations.
* For the sencond answer we do need O(m*log(m))+O(n+m) = O(m*log(m)+n+m)
operations.
These terms are hard to compare but a plot shows that insertList_foldl
should be faster than insertList_union.
But a testprogram shows that insertList_union is faster (and needs less
memory) whatever the sizes of n and m are.
So my questions are:
Why are the insertList* functions missing?
How would the library implementors implement insertList* and why?
thanks,
--
-- Mirko Rahn -- Tel +49-721 608 7504 --
--- http://liinwww.ira.uka.de/~rahn/ ---
More information about the Libraries
mailing list