Proposal: more general unionWith for Data.Map
Bertram Felgenhauer
bertram.felgenhauer at googlemail.com
Wed Jan 25 16:45:05 CET 2012
Milan Straka wrote:
> Anyway, we could instead of proposed unionWithKey offer functions
> mergeWith :: Ord k => (Maybe a -> Maybe b -> Maybe c) -> Map k a -> Map k b -> Map k c
> mergeWithKey :: Ord k => (k -> Maybe a -> Maybe b -> Maybe c) -> Map k a -> Map k b -> Map k c
> The combining function is executed for every unique key from both maps.
> All functions unionWith, intersectionWith, differencseWith, proposed
> unionWith can be expressed using this function.
>
> But I am not sure about the performance (using so many Maybes).
There's a bigger problem with performance than this constant factor,
namely that it's no longer possible to short-cut evaluation for
subtrees of the map that are known to be disjoint. For example,
empty `intersect` x currently can be computed in constant time,
no matter what x is; this can not be done with `merge`.
This reasoning justifies the existence of intersection, union and
difference functions in Data.Map in addition to a merge function.
Of course, the functions union, intersect and difference could be
implemented as a single function that takes two boolean arguments
to specify which of the disjoint parts to keep in the result.
Bertram
More information about the Libraries
mailing list