Understanding how to construct GHC.Generics Rep

Question

I'm trying to learn about how to use GHC.Generics. A fascinating topic but daunting.

While reading through the blog entry 24 Days of GHC Extensions: DeriveGeneric, I learned how to take a value and navigate its Rep. Okay.

However, reading the blog entry Building data constructors with GHC Generics which describes the analog of constructing the Rep and converting it back to a value, I got stumped. I've read through a number of other resources, but to no great help.

In the blog entry is the following code. First, constructing the Rep:

class Functor f => Mk rep f | rep -> f where
  mk :: f (rep a)

instance Mk (K1 i c) ((->) c) where
  mk = \x -> K1 x

instance (Mk l fl, Mk r fr) => Mk (l :*: r) (Compose fl fr) where
  mk = Compose (fmap (\l -> fmap (\r -> l :*: r) mk) mk)

instance (Mk f f') => Mk (M1 i c f) f' where
  mk = M1 <$> mk

Then, dealing with the Compose:

class Functor f => Apply f a b | f a -> b where
  apply :: f a -> b

instance Apply ((->) a) b (a -> b) where
  apply = id

instance (Apply g a b, Apply f b c) => Apply (Compose f g) a c where
  apply (Compose x) = apply (fmap apply x)

Then dealing with type ambiguity:

type family Returns (f :: *) :: * where
  Returns (a -> b) = Returns b
  Returns r = r

make :: forall b f z. (Generic (Returns b), Apply f (Returns b) b, Mk (Rep (Returns b)) f) => b
make = apply (fmap (to :: Rep (Returns b) z -> (Returns b)) (mk :: f (Rep (Returns b) z)))

Wow.

Really, I'm stuck at the very beginning, at the class Mk where mk returns a functor. My questions:

1. What is mk returning? Why is it a functor? What is the interpretation of its result? I can see that the K1 i c instance of Mk returns a function (I understand this is a functor) that takes a value and wraps it in K1, but mk for Mk (l :*: r) and Mk (M1 i c f) are completely lost on me.

2. I'm guessing Compose comes from Data.Functor.Compose, which means that when I do fmap f x, it does the fmap two levels deep into the composed functors. But I can't make sense of the nested fmaps inside the Compose.

3. For the instance of M1 i c f, I thought it would just wrap the inner values in M1, so the need to M1 <$> mk or fmap M1 mk makes no sense to me.

Obviously I'm not grokking the intent or meaning of these instances and how these instances interact to create the final Rep. I am hoping someone can enlighten me and provide a good explanation of how to use GHC.Generics along the way.

Answer 1

1. What is mk returning?

Let's go through a much simpler example In the documentation of GHC.Generics first. To achieve a generic function encode :: Generic a => a -> [Bool] that bit serialize every data type which has a Generic instance, they defined the type class below :

class Encode' rep where
  encode' :: rep p -> [Bool]

By defining Encode' instances for every Rep type (M1, K1, etc.), they made the function work universally on every data types.

In Building data constructors with GHC Generics, the author's final goal is a generic function make :: Generic a => TypeOfConstructor a, so naively one may define:

class Mk rep where
  mk :: (? -> p) -- what should '?' be?

And soon realize that it's impossible due to a few problems:

1. ->, the function type in haskell only takes one argument at a time, so mk won't be able to return anything sensible if the constructor takes more than one argument.
2. The number and type of the arguments are unclear: it's relative to the rep type in concern.
3. It cannot be plain p as the result type. Without the rep context it's impossible to derive instances for :*: or :+:, and the function will no longer work on any nested data type.

Issue 1 can be solved with Data.Functor.Compose. A function of type a -> b -> c can be encoded into Compose ((->) a) ((->) b) c, it can be further composed while keeps a whole lot of information about argument types. And by making it a type parameter of Mk, issue 2 is solved too:

class Functor f => Mk rep f | rep -> f where
  mk :: f (rep p)

where f is generalization over Compose f g and (->) a, which contains type-level information to construct a rep p, i.e. everything before the final -> in a -> b -> c -> ... -> rep p.

2. I'm guessing Compose comes from Data.Functor.Compose, which means that when I do fmap f x, it does the fmap two levels deep into the composed functors. But I can't make sense of the nested fmaps inside the Compose.

In the Mk instance of :*::

instance (Mk l fl, Mk r fr) => Mk (l :*: r) (Compose fl fr) where
  mk = Compose (fmap (\l -> fmap (\r -> l :*: r) mk) mk)

fmap changes only the inner-most type of a nested Compose, in this case changes the final result of a n-ary function. mk here is literally concatenating two argument lists fl and fr, putting their results into a product type, namely

f :: Compose ((->) a) ((->) b) (f r)
g :: Compose ((->) c) ((->) d) (g r)
mk f g :: Compose (Compose ((->) a) ((->) b)) (Compose ((->) c) ((->) d)) ((:*:) f g r)

-- or unwrapped and simplified
(a -> b -> r) -> (c -> d -> r') -> a -> b -> c -> d -> (r, r')

3. For the instance of M1 i c f, I thought it would just wrap the inner values in M1, so the need to M1 <$> mk or fmap M1 mk makes no sense to me.

It does just wrap the inner values in M1, but it's unclear how long the argument list of the underlying f is. If it takes one argument then mk is a function, otherwise it's a Compose. fmap wraps the inner-most value of them both.