How to implement Data.Map.insertList*?
Keean Schupke
k.schupke at imperial.ac.uk
Wed Feb 23 09:07:42 EST 2005
Would it not be more efficient to put the list into a new map, and then
merge the old and new maps (a bit like
the sort and merge technique used in old tape databases)...
Keean.
Mirko Rahn wrote:
>
> 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,
>
More information about the Libraries
mailing list