#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: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:1 RyanGlScott]:

Forgive my ignorance here, but how are you proposing to inline the inner `traverse`?

In my mind, the only way I can see how you'd remove the `(<$>)` is if you had a special case for `ZipList []`.

You're confused about the definition. {{{#!hs newtype ZipList a = ZipList [a] }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13153#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: | -------------------------------------+------------------------------------- Comment (by dfeuer): We have (essentially) {{{#!hs instance Traversable [] where traverse f = foldr cons_f (pure []) where cons_f x = liftA2 (:) (f x) }}} Manually copying this idea into the `ZipList` instance (I guess it's more than inlining) gives {{{#!hs instance Traversable ZipList where traverse f = foldr cons_f (pure (ZipList [])) .# getZipList where cons_f x = liftA2 (\x' ys' -> ZipList (x' : getZipList ys')) (f x) }}} The point is to fuse the final `ZipList <$>` into an operation that needs to happen anyway. `ZipList` is actually a terrible choice of example, because lists ''usually'' aren't short enough for this to matter much. But if you look at something like `First` or `Sum` it's more obviously silly. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13153#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: | -------------------------------------+------------------------------------- Comment (by nomeata): The `fmap` in {{{ instance Traversable ZipList where traverse f (ZipList xs) = ZipList <$> traverse f xs }}} is not polymorphic, but rather a concret one (the one from `Functor []`), right? I would expect that to be resolved to actual `map`, for which we have a `map/coerce` rule, which should optimize the whole `ZipLib <$>` stuff away. Did you check the core if there is really an `fmap` or `map` left? If so, then the rules don't work as expected, and that is a bug. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13153#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:5 RyanGlScott]:

{{{#!hs newtype ZipList a = ZipList [a] deriving newtype (Functor, Foldable) deriving unsafenewtype (Traversable) }}}

Interesting. I believe this is probably safe even if the underlying `Applicative` and `Traversable` are bogus, thanks to polymorphism. We are coercing `f (t b)` to `f (u b)`. The usual concern with such a coercion is that `f` could have an index rather than a parameter, so matching on the result of the coercion could falsely reveal that `t ~ u`. But `traverse` can only construct `f` values using `pure`, `<*>`, and the given function. Of those, only the given function could produce values carrying evidence. But they can carry evidence only about `b`, not about `t`. So it looks like coercing the result of `traverse` to a representationally identical container with the same element type is ''probably'' okay.

Granted, this is a separate hack to get around the fact that we don't have higher-kinded roles yet, but it's (IMO) much nicer to use than having to manually inline the definition of `traverse` like you demonstrated above.

Can you explain how higher-kinded roles would help? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13153#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: | QuantifiedContexts 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): * keywords: => QuantifiedContexts Comment: I'm adding the `QuantifiedContexts` keyword only because implementing that feature (in the context of `GeneralizedNewtypeDeriving`) would make this feature request obsolete. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13153#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13153: Several Traversable instances have an extra fmap -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Core Libraries | Version: 8.1 Resolution: | Keywords: | QuantifiedConstraints 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: | -------------------------------------+------------------------------------- Comment (by RyanGlScott): Oh dear. I now realize that my heart was in the right place when I wrote comment:9, but I goofed up several key details. I had written this instance: {{{#!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)) }}} But this is not quite what I wanted. The `f` in the instance context is not the same `f` as the `f` in the type signature as `traverse`, which is crucial. Indeed, the quantified constraint shouldn't go in the instance context at all, but rather in the method type signature itself: {{{#!hs instance Traversable inner => Traversable (Wrapped inner) where traverse :: forall f a b. (Applicative f, forall p q. Coercible p q => Coercible (f p) (f q)) => (a -> f b) -> Wrapped inner a -> f (Wrapped inner b) traverse = coerce (traverse :: (a -> f b) -> Wrapped inner a -> f (Wrapped inner b)) }}} Of course, this isn't going to work either, because that's not actually the type signature for `traverse`. If only that were the case! But wait, there's something interesting going on here. `f` is an instance of `Applicative` and in turn an instance of `Functor`. What exactly //is// `Functor`, anyway? Here's the definition we all know and love: {{{#!hs class Functor f where fmap :: (a -> b) -> f a -> f b }}} If you squint really hard and look at the type signature for `fmap`, it says "if you give me a coercion from `a` to `b`, then I can produce a coercion from `f a` to `f b`. That's awfully close to `forall a b. Coercible a b => Coercible (f a) (f b)`! I'm going to be bold add suggest adding just that as a superclass of `Functor`: {{{#!hs class (forall a b. Coercible a b => Coercible (f a) (f b)) => Functor f }}} (This is adapted from a similar suggestion [https://ghc.haskell.org/trac/ghc/ticket/9123#comment:3 here], which predates `QuantifiedConstraints`.) If we did this, we'd be able to newtype-derive `Traversable` instances with no further changes, which is awesome! The downside, of course, is that we'd have to add a quantified constraint as a superclass of a Haskell Report class, at which many people would (understandably) turn up their noses. If that option is too unpalatable, an alternative would be to add an additional class method to `Traversable` with the right context: {{{#!hs class (Functor t, Foldable t) => Traversable t where traverse :: Applicative f => (a -> f b) -> t a -> f (t b) traverse' :: (Applicative f, forall p q. Coercible p q => Coercible (f p) (f q)) => (a -> f b) -> t a -> f (t b) traverse' = traverse }}} Then, folks who really care about performance could implement `traverse' = coerce (traverse' :: ...)` themselves and use that. However, you still wouldn't be able to newtype-derive `Traversable` with this approach, and it's rather unsatisfying in that performance-minded programmers would have to switch over all of their `traverse`s to `traverse'`s. (And arguably, //every// programmer should be performance-minded anyway!) In any case, this situation is clearly more complicated than I originally imagined, and I imagine that any solution we could pick will have its share of drawbacks. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13153#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler