Type-level generics

[Wolfgang Jeltsch]

Am Samstag, den 02.09.2017, 11:35 -0400 schrieb Ryan Scott:
> > When I looked at it the last time, there were some apparent
> > leftovers in the form of types or type parameters never used.
>
> Are you referring to the `p` type parameters that are found in most of
> the data types in GHC.Generics?

No, there were really unused things.

> If so, they are most definitely used—try deriving Generic1 to see this
> in action!

I know that they are needed for Generic1, but they are not needed for
Generic.

> It's true that in the context of Generic (without the 1 at the end)
> the `p` isn't used, but this is by design, as this allows us to share
> the same representation types across Generic and Generic1.

It would be great if we could employ kind polymorphism or even type-in-
type to have a single set of representation types, but still no unused
parameters.

> > there is no possibility to work with types with more than one
> > parameter.
>
> Quite true. But I posit that engineering GHC.Generics to work with
> more than one type parameter at a time is much harder than it sounds.
> After all, to profitably work with even a *single* type parameter
> (what Generic1 does), we must bring in three additional representation
> types: Par1, Rec1, and (:.:), depending on where in the datatype the
> last type parameter occurs. If we wanted to have, say, Generic2, we'd
> similarly need to be able to work with many more combinations of type
> parameter positions, such as:
> 
> * data Foo1 a b = Foo1 a b
> * data Foo2 a b = Foo2 (Either a b)
> * data Foo3 a b = Foo3 (Either b a)
> * etc.

Actually, I am looking for something even bigger: not just a Generic2
class, but a Generic class that can deal with types of any arity.

> A naïve approach would be to tack on another type parameter at the end
> of every representation type, and introduce more types to deal with
> all the combinations of the first and second type parameter that could
> arise. But this approach doesn't scale well—after all, at what number
> N do you stop introducing new representation types?

We should nowhere stop, but allow an arbitrary number of parameters. ☺
Maybe through striving for a Generic class that works with arbitrary
arities, we will find some deeper pattern, which could relieve us from
having ad-hoc types such as the Foo1, Foo2, and so on you mention above.

> So extending GHC.Generics to deal with more than one type parameter is
> far from obvious to me

It is also far from obvious for me. 😉 I actually think that makin
g GHC.Generics more generic (making it work with types of arbitrary
arity) is a nice research task, not something than can be done very
easily.

>  (let alone whether it could be made backwards compatible with the
> current API).

It should not be backwards compatible. If we insist on backwards
compatibility, we can never arrive at a version that works with types of
any arity.

> > the GHC.Generics module looks a bit unpolished and ad-hoc at the
> > moment.
>
> Yes, quite literally everything in GHC.Generics is one large, ad hoc
> hack. But it's also a darn useful one :)

I am worried that people get so much used to the current interface that
it will be hard to change it for something better later. You already
argued in favor of backwards compatibility. ☹

All the best,
Wolfgang