[GHC] #1460: Problem with Monoid instance of Data.Map

[GHC]

#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