Introduce typeclasses making it easier to write generic extension methods

[julienrf]

Fixes #294.

[julienrf]

Here is a design that make it possible to define a decorator that will work for any collection-like type, whether it is a collection (e.g. Seq[Int]), a view (e.g. SeqView[Int]) or something that can be seen as a collection (e.g. String). It is possible to program generically against this decorated type (and extract their type of elements).

1. A decorator is an implicit class that takes an implicit HasXxxOps, where Xxx can be Set, Seq, etc.:

implicit class SeqDecorator[C, S <: HasSeqOps[C]](coll: C)(implicit val seq: S) { … }

(note that if https://github.com/lampepfl/dotty/issues/3964 or https://github.com/scala/bug/issues/5712 were solved we could just write the following: implicit class SeqDecorator[C](coll: C)(implicit val seq: HasSeqOps[C]))

The definition of HasSeqOps is the following (largely inspired from the old IsSeqLike):

trait HasSeqOps[C] {
  type A
  def apply(c: C): SeqOps[A, _, _]
}

The type HasSeqOps contains a type member A referring to the type of elements of the decorated collection. For instance, if we decorate a List[Int] we would get seq.A =:= Int. Here is an example of use to set a lower bound on type a parameter taken by the extension method:

  def intersperse[B >: seq.A](sep: B) = …

2. Extension methods can use BuildFrom to compute their result type.

  def intersperse[B >: seq.A, That](sep: B)(implicit bf: BuildFrom[C, B, That]): That =
    bf.fromSpecificIterable(coll)(new View.Intersperse(seq(coll), sep))

The drawbacks of this design are:

• decorators take two parameters, and thus can not be made value classes,
• it is often hard to understand why an implicit HasXxxOps[C] instance has not be found for a given type C.

[Ichoran]

The strategy looks sound overall, though I do worry that the complexity will seem daunting to people even if mostly it "just works". We'll need some good documentation.

Also, I think we could improve the usability a bit (as indicated on my comments for HasImmutableMapOps, but they apply to everything).

[julienrf]

In any case, this framework mainly targets advanced users.

A first support of generic decorators is already provided by BuildFrom (exactly like we used to do with CanBuildFrom in the old collections). This allows users to generically define extension methods for any collection type but views, String and Array. This should be fine for most cases.

If one needs more power (ie the ability to also abstract over views, String and Array), then HasIterableOps and friends are the right tool to use.

Last, I’ve put this machinery in the collections-contrib module. We don’t have to have it in the core.

[julienrf]

Rebased

[julienrf]

@szeiger any objection to merge this one?