Adrian Hey wrote:
The type of the proposed merge now seems similarly strange to me..
merge :: (k -> Maybe a -> Maybe b -> Maybe c) -> map a -> map b -> map c
This requres users to define a function argument that is presumably of form
f k Nothing Nothing = undefined f k (Just a) Nothing = fa k a f k (Just a) (Just b) = fab k a b f k Nothing (Just b) = fb k b
Why not just pass fa,fab and fb directly, which will be more convenient for both users and implementors I think..
merge :: (k -> a -> Maybe c) -> (k -> a -> b -> Maybe c) -> (k -> b -> Maybe c) -> map a -> map b -> map c
While every such f must have this form, in the sense that \f k -> (\a -> f k (Just a) Nothing , \a b -> f k (Just a) (Just b), \b -> f k Nothing (Just b)) is an isomorphism, it doesn't mean that it's explicitly implemented that way. The intention was that the library exports ready-made functions union, intersect, difference :: k -> Maybe a -> Maybe a -> Maybe a and combinators like unionWith :: (k -> a -> b -> c) -> (k -> Maybe a -> Maybe b -> Maybe c) that can be plugged into merge , like merge intersect merge (unionWith $ curry snd) Thus, the user doesn't implement the argument to merge himself unless he requires custom behavior. Hence, using one argument instead of three is more convenient here. The particular form union, intersect, difference :: Maybe a -> Maybe a -> Maybe a has mnemonic value as well, since Maybe a is the finite map with one element, so the combinator intersect actually intersects two finite maps. You're probably right concerning the efficiency of merge . The problem is that merge may decide per element whether to intersect, union, difference or something, while the original intersect may only intersect elements and can hence throw whole subtrees away without looking into them. An signature for merge that does not allow per-element tests would be merge :: (Bool -> Bool -> Bool) -> (k -> a -> b -> c) -> map a -> map b -> map c Here, the boolean function determines membership while the second argument determines how to merge two values. There is the small problem that the boolean function f ought to fulfill f False False = False. This can be guaranteed by using a rank-2 type merge :: (forall a. Maybe a -> Maybe a -> Maybe a) -> ... Incidentally, this restores the fact that the first argument combines one-element finite maps. Regards, apfelmus