#1460: Problem with Monoid instance of Data.Map -------------------------------------+------------------------------------- Reporter: ahey@… | Owner: (none) Type: proposal | Status: closed Priority: normal | Milestone: Not GHC Component: libraries/base | Version: 6.6.1 Resolution: fixed | Keywords: Data.Map | Monoid Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by andrewthad): What I'm trying to argue is that the two possible `Monoid` instances for `Map` aren't really equal in terms of how much they buy you. Let's look at merging nested `Map`s again. The question here is "how much code do I have to write to merge these?" Both for a deep merge and for a shallow merge. {{{ type M = Map Int (Map Char (Map PersonId (Map ItemId (Set Foo)))) -- Assuming the current Monoid instance of Map deep,shallow :: M -> M -> M deep = unionWith (unionWith (unionWith (unionWith (<>)))) shallow = (<>) -- Assuming the value-combining Monoid instance of Map deep,shallow :: M -> M -> M deep = (<>) shallow = union }}} My point is that the value-combining instance helps us more than the left- biased instance. Since the instances chain together, it's just one type we're getting a better `Monoid` instance for. It's any arbitrary nesting of them. Let's look at a situation where the left-biased instance fares a little better. What about the situations where you want a left-biased merge at the bottom of a nesting of `Monoid`s? So, not a nesting of `Map`s, but a nesting of other `Monoid`s with a `Map` at the bottom: {{{ type K = Int -> Char -> IO ([ParseError],Map PersonId Person) }}} The left-biased instance has the desirable behavior here. If, after have concatenated a bunch of expressions of type `K`, we try to parse two people with the same id, we silently discard the second one. But, we can easily recover this same behavior with the value-combining `Monoid` instance with: {{{ foo :: Int -> Char -> IO ([ParseError],Map PersonId (First Person)) }}} If you don't actually want that `First` newtype in your final result, it can be `coerce`d away safely as a noop. So, since the value-combining instance can express the left-biased instance, even in the worst cases, the semantics of the left-biased instance can be recovered by clever use of `coerce`. However, the reverse is not true. The left-biased instance cannot express the value-combining union, so currently when we want this, we have to step outside the realm of `Monoid` instances entirely and manually do the lifting. Just to emphasize the asymmetry in the amount and kind of code the end user must write: {{{ type J = Bar -> Baz -> IO ([Log], Map Pokemon (Set Attack)) type V = Bar -> Baz -> IO ([Log], Map Identifier Name) leftBiased :: V -> V -> V valueMerging :: J -> J -> J -- with the left-biased Monoid instance leftBiased = (<>) valueMerging v1 v2 a b = liftA2 (\(x1,y1) (x2,y2) -> (x1 <> x2, unionWith (<>) y1 y2)) (v1 a b) (v2 a b) -- with the value-merging Monoid instance type V' = Bar -> Baz -> IO ([Log], Map Identifier (First Name)) leftBiased a b = coerce ((coerce a) <> (coerce b :: V')) valueMerging = (<>) }}} I know using `coerce` isn't the prettiest thing, but notice that with the value-merging `Monoid` instance, we are able to leverage the automatic lifting of `Monoid` instances to give us a desired behavior. With the left-biased instance, we're stuck doing this by hand. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/1460#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler