[GHC] #8516: Add (->) representation and the Invariant class to GHC.Generics

[GHC]

#8516: Add (->) representation and the Invariant class to GHC.Generics
-------------------------------------+-------------------------------------
        Reporter:  nfrisby           |                Owner:
            Type:  feature request   |               Status:  new
        Priority:  low               |            Milestone:
       Component:  Compiler (Type    |              Version:  7.7
  checker)                           |
      Resolution:                    |             Keywords:
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 RyanGlScott):

 Well, I had previously thought one could get away with not considering
 `Invariant`, but after thinking about it some more, having `Invariant` is
 crucial for this new feature to be compositional.

 We'd add two new data types:

 {{{#!hs
 infixr 4 :->:, :->-:
 newtype (f :->: r)  p = ContraArrow1 { unContraArrow1 :: f p -> r   }
 newtype (f :->-: g) p = InvArrow1    { unInvArrow1    :: f p -> g p }
 }}}

 And, if we [https://ghc.haskell.org/trac/ghc/ticket/7492 change] `Rec1 f`
 to `f :.: Par1`, then we can also define the following for symmetry:

 {{{#!hs
 infixr 4 :>-:
 type (r :>-: f) = ((->) r) :.: f
 }}}

 (I've adopted a pretty arbitrary naming scheme where hyphens (`-`) denote
 occurrences of the type parameter. Feel free to suggest other names.)

 Then we can generate instances for data types no matter which side of an
 arrow a type parameter might occur. Here is an example:

 {{{#!hs
 newtype Endo a = Endo (a -> a) deriving Generic1

 instance Invariant Endo where
   invmap f g (Endo x) = Endo (f . x . g)

 ==>

 instance Generic1 Endo where
   type Rep1 Endo = D1 ... (C1 ... (S1 ... (Par1 :->-: Par1)))
   to1 (M1 (M1 (M1 c))) = Endo ((.) (invCompose unPar1 Par1) unInvArrow1 c)
   from1 (Endo c) = M1 (M1 (M1 ((.) InvArrow1 (invCompose Par1 unPar1) c)))

 invCompose :: (c -> d) -> (a -> b) -> (b -> c) -> a -> d
 invCompose = \f g h x -> f (h (g x))
 }}}

 So far, so good. But if we define something like this:

 {{{#!hs
 newtype Endo2 a = Endo2 (Endo a) deriving Generic1
 }}}

 Then things become awkward. GHC would attempt to generate an instance like
 this:

 {{{#!hs
 instance Generic1 Endo2 where
   type Rep1 Endo2 = D1 ... (C1 ... (S1 ... (Endo :.: Par1)))
   to1 (M1 (M1 (M1 c))) = Endo2 ((.) (fmap unPar1) unComp1 c)
   from1 (Endo2 c) = M1 (M1 (M1 ((.) Comp1 (fmap Par1) c)))
 }}}

 But this will never work, because it assumes `Endo` is a `Functor`
 instance, which can't happen. This is quite a problem: we can make one
 datatype a `Generic1` instance, but we can't make a simple `newtype`
 wrapper around it a `Generic1` instance!

 However, if we changed the way GHC generated code for the `:.:` case to
 assume that the outermost datatype is an `Invariant` instance, not a
 `Functor` instance, then it would work:

 {{{#!hs
 instance Generic1 Endo where
   type Rep1 Endo = D1 ... (C1 ... (S1 ... (Par1 :->-: Par1)))
   to1 (M1 (M1 (M1 c))) = Endo ((.) (invCompose unPar1 Par1) unInvArrow1 c)
   from1 (Endo c) = M1 (M1 (M1 ((.) InvArrow1 (invCompose Par1 unPar1) c)))
 }}}

 Of course, this would mean bringing in `Invariant` to `base`, and it makes
 an assumption that most datatypes you'd find in the wild are `Invariant`
 instances already. As I mentioned above, trying to make `Invariant` a
 superclass of `Functor` is a hard sell.

 Futhermore, I'm not sure if we'd really gain anything after all this
 breakage besides being able to derive `Functor` and `Invariant` instances
 generically. I'm not convinced the benefits outweigh the potential
 heartburn in this case.

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