[scalaz] Code generation of type class instances for 2.8 collections

[Jason Zaugg]

The SBT build for module scalaz-core now generates boilerplate
instances of various type classes for the 2.8 collections heirachy.
The generated files are not checked in.

Generator: ./project/build/Boilerplate.scala

Sample generated file:
./core/src_managed/main/scala/scalaz/BindCollections.scala

At the moment this is run unconditionally before the compile task in
this module, which prevents quick incremental recompilation of the
project. I'll find a way to improve this soon.

Review welcome:
http://github.com/scalaz/scalaz/commit/4e97f3983241170ed14408ed989d6769e1d565df

-jason

--
You received this message because you are subscribed to the Google Groups "scalaz" group.
To post to this group, send email to sca...@googlegroups.com.
To unsubscribe from this group, send email to scalaz+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/scalaz?hl=en.

[Ben Hutchison]

On Mon, Apr 26, 2010 at 8:05 AM, Jason Zaugg <jza...@gmail.com> wrote:
> The SBT build for module scalaz-core now generates boilerplate
> instances of various type classes for the 2.8 collections heirachy.

In your commit comment, you suggest that the changed collection design
has forced the need for this generation, which includes most pairwise
combinations from Typeclasses X CollectionClasses.

Im interested to understand what it is about the new API structure
that now requires this?

-Ben

[Jason Zaugg]

Hi Ben.

Start by look at this type signature of this method:

trait TraversableLike[+A, +Repr] {
/** The type implementing this traversable */
protected type Self = Repr

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B,
That]): That = {
val b = bf(repr)
for (x <- this) b += f(x)
b.result
}
}

It does not guarantee that all subclasses of TraversableLike can be
treated as a Functor:

trait Functor[F[_]] {
def fmap[A, B](r: F[A], f: A => B): F[B]
}

The motivations for this are described in the paper "Fighting Bit Rot
with Types" [1]. Basically, map need not return a collection of the
same static type as the original collection, to allow such
flexibility:

scala> Map(1 -> 2).map(identity)
res1: scala.collection.immutable.Map[Int,Int] = Map((1,2))

scala> Map(1 -> 2).map(_ => 0)
res2: scala.collection.immutable.Iterable[Int] = List(0)

This move removes a lot of duplicated code from the collections
library itself, and allows Maps, Strings, Arrays, and BitSets to
squeeze into the same API. The cost is that you can't abstract over
the type of the collection (upcasting to Traversable doesn't count!)

This seems to be throwing the baby out with the bathwater.
Fortunately, by generating [2] instances of the scalaz.Functor type
class for well behaved members of the collections heirarchy, we can
abstract again!

scala> Traversable(1) ∘ identity
res8: Traversable[Int] = List(1)

scala> Iterable(1) ∘ identity
res9: Iterable[Int] = List(1)

scala> Seq(1) ∘ identity
res10: Seq[Int] = List(1)

There is one outstanding problem: now that I have defined type class
instances for both leaf and non-leaf nodes of the inheritance tree,
there are some ambiguities in the implicit search / type inference.
This happens when the type class is variant in the type parameter. For
example, I just noticed:

scala> implicitly[Zero[Iterable[Int]]]
<console>:12: error: ambiguous implicit values:
both method MutableListBufferZero in trait ZeroCollections of type
[A]scalaz.Zero[scala.collection.mutable.ListBuffer[A]]
and method IndexedSeqZero in trait ZeroCollections of type
[A]scalaz.Zero[IndexedSeq[A]]
match expected type scalaz.Zero[Iterable[Int]]
implicitly[Zero[Iterable[Int]]]

We're gradually making the type classes invariant to fix this.
Subtyping makes life very difficult!

-jason

[1] http://drops.dagstuhl.de/opus/volltexte/2009/2338/pdf/09005.OderskyM.2338.pdf
[2] http://github.com/scalaz/scalaz/commit/4e97f3983241170ed14408ed989d6769e1d565df#L12R31