New Collections: can we decrease the noise level?

12 replies

Sat, 2009-11-14, 20:49

dcsobral

Joined: 2009-04-23,

Here are a couple of functions I wrote lately:

def quicksort


  [T, CC[X] <: Traversable[X] with TraversableLike[X, CC[X]]]       // My type parameters


  (coll: CC[T])                                                     // My explicit parameter


  (implicit o: T => Ordered[T], cbf: CanBuildFrom[CC[T], T, CC[T]]) // My implicit parameters


  : CC[T] =                                                         // My return type


  if (coll.isEmpty) {


    coll
  } else {


    val (smaller, bigger) = coll.tail partition (_ < coll.head)


    quicksort(smaller) ++ coll.companion(coll.head) ++ quicksort(bigger)


  }

import scala.collection.breakOut


def mode


  [T, CC[X] <: Seq[X]](coll: CC[T])


  (implicit o: T => Ordered[T], cbf: CanBuildFrom[Nothing, T, CC[T]])


  : CC[T] = {


  val grouped = coll.groupBy(x => x).mapValues(_.size).toSeq


  val max = grouped.map(_._2).max


  grouped.filter(_._2 == max).map(_._1)(breakOut)


}

These are simplified already from algorithms I thought cleaner, but which required even more boilerplate. Also, they require importing stuff from scala.collection and scala.collection.generic. Here are some thoughts:
1. To fully use CC[X] <: Traversable[X], I need Traversable[X] with TraversableLike[X, CC[X]] with GenericTraversableTemplate[X, CC].
Without Traversable, I can't get companion (ie, no "empty" or "apply"). Without GenericTraversableTemplate, I can't get a companion that returns CC. Without TraversableLike, I can't get stuff like "++" to return CC.
This pretty much applies down the hierarchy of classes, but it is particularly important for the *generic* ones: Traversable, Iterable, Map, Set and Seq.
2. The implicit CanBuildFrom is pretty much required for anything. Having it means, as well, I can't use <% to simplify declarations.

I'm talking about a pattern that you, designers of Scala, have worked hard to achieve, because of how powerful it is. I suggest some thought must be put on how to simplify the usage of this pattern a bit. A couple of suggestions:
* Define something like:
type TraversableType[A, CC] = Traversable[A] with TraversableLike[A, CC[A]] with GenericTraversableTemplate[A, CC]
to make the type parameter declaration briefer and less redundant.
* Accept mixing <% and implicit parameters. Just append the implicitly declared implicits to the implicit parameter list.
Accept them or not, but please do something about the verbosity of these declarations.
About CanBuildFrom, if we had something like A : T for it, that would help a lot.
On a minor note, I haven't found any way to get at a CC[A]-returning companion except casting coll to GenericTraversableTemplate before getting the companion. Is there anything that can be done about it?
I'll just finish by stating the use case. I have CC[T] <: Traversable[T], with perhaps a T : Numeric or T <% Ordering. I want operations on coll: CC[T] to return CC[T]. There ought to be some way to state so in a brief manner.
-- Daniel C. Sobral

Veni, vidi, veterni.