milessabin/shapeless — pull request #35 by larsrh (2013-06-17 18:59:57+00:00)
Title: Turbocharge type class derivation: now with coproducts!

This is the current state of the affairs. First, the following things are working:

* automatically derive type class instances for algebraic data types with _zero_ boilerplate at use-site
* recursive ADTs, but not where the recursion is nested in some other type
* works for type classes which don't support coproducts, e.g. `Monoid` – obviously, only one-case ADTs are supported there
* the underlying machinery (can be seen in the `ADTReprs` trait) is _very_ flexible

Now, these things don't work (yet?):

* it utterly fails for parametric types, because I didn't yet figure out a good way to detect existential types. A complete solution should be able to support something general like this, where `F` is some reasonably well-behaved type constructor (i.e. a class, but better not a type member) and `B` is arbitrary¹:

```scala
trait Parametric[T]
case class Impl1[A](...) extends Parametric[F[A]]
case class Impl2(...) extends Parametric[B]
```

* mutually recursive data types, which can (probably) be added easily for some restricted cases

¹ or maybe it is cleverer to support a subset instead to avoid insanity

## Points for discussion

Consider this example:

```scala
sealed trait Super
case class Foo(i : Int, s : String) extends Super
case class Bar(i : Int) extends Super

Bar(0).show // what do you expect?
```

The problem is that you get wrong output. Why? The static type of `Bar(0)` is `Bar`. When asking for a show instance, the machinery sees a single case class and destructures that into `Int :: HNil`. However, we expected it to see `Super` and destructure it into its cases `Foo` and `Bar`, and so on. The underlying problem is an ambiguity: What is the ADT here, `Bar = Bar Int` or `Super = Foo Int String | Bar Int`?

As a fix, I propose an annotation which declares which data types are eligible, maybe `@adt` or something similar. Then, the macro could inspect the type, climb up the inheritance ladder, and find the first one with an `@adt` annotation, and use that. This would also solve another problem neatly, namely how to detect mutual-ness. Consider:

```scala
sealed trait A
case class A1(..., rec: B) extends A

sealed trait B
case class B1(..., rec: A) extends B
```

How is the macro supposed to know that `A` and `B` are mutually recursive? It _could_ just go and look into all the participating types, but that heuristic falls flat in at least two cases:

1. A user wants to supply her own, hand-written instance for `B`, e.g. when the `A` part of `B` does not contribute to the instance.
2. When it's not `rec: B` but something like `rec: List[B]`. We would need to dig into arbitrary types to find out where something is referenced.

So, an annotation would be in order:

```scala
@adt(mutual = true) sealed trait A
@adt(mutual = true) sealed trait B
```

That would tackle at least the first one of the above mentioned problems: Just don't specify `mutual = true` and let the usual implicit resolution mechanism discover an instance for `B`, never mind what's inside there. For the second one, I have no idea. We would somehow need a way to tell the macro how it can tie the knot when other type constructors are in the way.

## Integration into the rest of shapeless

I did snoop around sybclass a bit, but unfortunately, I couldn't tell how the things I mentioned are tackled there, or how we could unify both macro implementations. Some explanation would be appreciated, now that you can have a look at the whole of my source code :-)

## Plans?

It occured to me that what I wrote doesn't necessarily has to go into shapeless proper, and I can understand if you don't like it because of it's shortcomings/redundancy/… If so, I'd like to propose the following action plan:

1. Put it into shapeless-contrib.
2. Remove `TypeClass` from shapeless proper.
3. Let my implementation mature, and find out which parts can be shared.
4. ???
5. PROFIT!!!