[GHC] #13153: Several Traversable instances have an extra fmap

[GHC]

#13153: Several Traversable instances have an extra fmap
-------------------------------------+-------------------------------------
        Reporter:  dfeuer            |                Owner:  dfeuer
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:  8.4.1
       Component:  Core Libraries    |              Version:  8.1
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Runtime           |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by RyanGlScott):

 * cc: goldfire (added)


Comment:

 > Can you explain how higher-kinded roles would help?

 Hm, I thought I meant higher-kinded roles, but now I recall Richard
 telling me that he thought those were inferior to normal roles +
 [https://ghc.haskell.org/trac/ghc/ticket/2256 implication constraints]
 (I've cc'd him in case I totally butcher this). So let me instead explain
 how those would help :)

 The current issue that prevents you from writing this:

 {{{#!hs
 newtype Wrapped inner a = Wrap { unwrap :: inner a }
   deriving (Functor, Foldable)

 instance Traversable inner => Traversable (Wrapped inner) where
   traverse = coerce traverse
 }}}

 is that we need to coerce from `(a -> f b) -> inner a -> f (inner b)` to
 `(a -> f b) -> Wrapped a -> f (Wrapped b)` for some `f`. That is, we need
 to prove `Coercible (f (inner b)) (f (Wrapped b))`. But we don't know this
 //a priori//. `f` is some arbitrary type variable, so we have to be
 conservative and assume its role is nominal. That prevents us from
 coercing underneath `f`, so we can't conclude `Coercible (f (inner b)) (f
 (Wrapped b))`.

 But what if we could modify the `Traversable` instance to require this
 coercibility property as part of the instance context? It sure would be
 great if we could just write this:

 {{{#!hs
 instance (Coercible (f (inner b)) (f (Wrapped inner b)), Traversable
 inner) => Traversable (Wrapped inner) where
   traverse :: forall f a b. Applicative f => (a -> f b) -> Wrapped inner a
 -> f (Wrapped inner b)
   traverse = coerce (traverse :: (a -> f b) -> Wrapped inner a -> f
 (Wrapped inner b))
 }}}

 But sadly, this won't work, since the `b` and the `f` in in the instance
 context can't scope over the class methods.

 What [https://ghc.haskell.org/trac/ghc/ticket/9123#comment:29 implication
 constraints] would let you do here is write this:

 {{{#!hs
 instance (forall f b. Applicative f => Coercible (f (inner b)) (f (Wrapped
 inner b)), Traversable inner) => Traversable (Wrapped inner) where
   traverse :: forall f a b. Applicative f => (a -> f b) -> Wrapped inner a
 -> f (Wrapped inner b)
   traverse = coerce (traverse :: (a -> f b) -> Wrapped inner a -> f
 (Wrapped inner b))
 }}}

 Notice that we're now able to stick a `forall` inside of an instance
 context, something which GHC currently forbids! The idea here being that
 this `forall f a b. Applicative f => Coercible (f (inner b)) (f (Wrapped
 inner b))` would get fed into the constraint solver and could be used to
 conclude that `Coercible (f (inner b)) (f (Wrapped b))` works for //any//
 `f` and `b` (where `f` is `Applicative`).

 But do keep in mind that user-visible implication constraints are nothing
 but a feature request at the moment, so all the above is hypothetical.
 Until some wonderful day in the future when we have this, the escape hatch
 is `unsafeCoerce`.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13153#comment:9>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler