#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