How do I define a custom collection interface in Scala without defining an implementation?

Question

I'm trying to define a custom collection interface in Scala 2.8. I want to require that subclasses be Traversable, plus some other behavior. I also want methods like map() to return the appropriate type, as below:

trait CustomCollection[+A] extends Traversable[A] {
    def customOperation(i:Int):Int // for example
}

def incrementAll(c:CustomCollection[Int]):CustomCollection[Int] = c.map { _ + 1 }

This doesn't compile, because CustomCollection.map() returns a Traversable. I suppose I need to define a CanBuildFrom, but then I need to define an apply() method that constructs an instance from scratch. I don't want to specify a way to construct this; that should be up to the implementer. Is this possible?

Answer 1

If you want map to return a more specific collection type, then you should also inherit TraversableLike, with the second type parameter (representation type) set to CustomCollection[A].

Next, map requires an implicit parameter of type CanBuildFrom. It will look in the companion object of CustomCollection to find a conforming implicit value of that type. If you take a look at the source code of Seq classes, you will see that their companions provide CanBuildFrom objects of type GenericCanBuildFrom which forwards the call for the builder back to the collection that requested the builder. That way, the dynamic type of return type of Seq transformer methods (e.g. map) is always the same as the type of the sequence itself.

What you have to do is:

1. Make CustomCollection[A] inherit TraversableLike
2. Make CustomCollection[A] inherit GenericTraversableTemplate
3. Make a companion object of CustomCollection and add an implicit which returns a GenericCanBuildFrom
4. Provide a default implementation for the builder in the CustomCollection companion

The implementers of CustomCollection will need to provide companion objects which have builder implementations and implicit CanBuildFrom objects (which can simply be GenericCanBuildFroms).

EDIT:

GenericTraversablTemplate mentioned above is needed because it first ensures that the collection will have the genericBuilder method called by the GenericCanBuildFrom builder factory. Second, it ensures that the collection actually has the companion object of type GenericCompanion.