Jay Taylor's notes

back to listing index

generics - scala 2.8 CanBuildFrom - Stack Overflow

[web search]
Original source (stackoverflow.com)
Tags: stackoverflow.com
Clipped on: 2012-08-13

Following on from another question I asked, I wanted to understand a bit more about the Scala method TraversableLike[A].map whose signature is as follows:

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That

Notice a few things about this method:

  • it takes a function turning each A in the traversable into a B
  • it returns That and takes an implicit argument of type CanBuildFrom[Repr, B, That]

I can call this as follows:

> val s: Set[Int] = List("Paris", "London").map(_.length)
s
: Set[Int] Set(5,6)

What I cannot quite grasp is how the fact that That is bound to B (i.e. it is some collection of B's) is being enforced by the compiler. The type parameters look to be independent in both the signature above and in the signature of the trait CanBuildFrom itself:

trait CanBuildFrom[-From, -Elem, +To]

How is the scala compiler ensuring that That cannot be forced into something which does not make sense?

> val s: Set[String] = List("Paris", "London").map(_.length) //will not compile

EDIT - this question of course boils down to: How does the compiler decide what implicit CanBuildFrom objects are in scope for the call?

asked Nov 12 '09 at 10:38
Image (Asset 1/3) alt=48.7k11122282

93% accept rate
add comment

2 Answers

up vote 22 down vote accepted

Note that the second argument to map is an implicit argument. There must be an implicit in scope with the appropriate types, or, otherwise, you must pass such an argument.

In your example, That must be Set[String], B must be Int and Repr must be List[String]. Therefore, for that to compile you need the following implicit object in scope:

implicit object X: CanBuildFrom[List[String], Int, Set[String]]

There's no such thing in scope. Also, breakOut can't provide it, because it, itself, needs an implicit CanBuildFrom, whose first type can be any class (a contra-variant descendent of Nothing), but otherwise restricted by the other types.

Take a look, for instance, on the CanBuildFrom factory from the companion object of List:

implicit def  canBuildFrom [A] : CanBuildFrom[List, A, List[A]]

Because it binds the second and third parameters through A, the implicit in question won't work.

So, how does one know where to look for, regarding such implicits? First of all, Scala does import a few things into all scopes. Right now, I can recall the following imports:

import scala.package._ // Package object
import scala.Predef._  // Object
// import scala.LowPriorityImplicits, class inherited by Predef
import scala.runtime._ // Package

Since we are concerned about implicits, note that when you import things from packages, the only implicits possible are singletons. When you import things from objects (singletons), on the other hand, you can have implicit definitions, values and singletons.

Right now, there are CanBuildFrom implicits inside Predef and LowPriorityImplicits, which are concerned with strings. They enable us to write "this is a string" map (_.toInt).

So, barring these automatic imports, and the explicit imports you make, where else can an implicit be found? One place: the companion objects of the instance on which the method is being applied.

I say companion object*s*, in the plural, because the companion objects of all traits and classes inherited by the class of the instance in question may contain relevant implicits. I'm not sure if the instance itself may contain an implicit. To be honest, I can't reproduce this right now, so I'm certainly making a mistake of some kind here.

At any rate, look inside the companion objects.

answered Nov 12 '09 at 12:48
Image (Asset 2/3) alt=95.4k12169345
  upvote
 flag
Daniel - how do I know what implicit objects are in scope at a given point in my code? That's what the question boils down to, I realize. Where is it specified? Also, this question has nothing to do with breakOut. – oxbow_lakes Nov 12 '09 at 13:17
  upvote
 flag
Apart from the implicit conversions in object scala.Predef, you have to either define the implicit in the same or an enclosing scope or you have to explicitly import that implicit. – Randall Schulz Nov 12 '09 at 15:33
  upvote
 flag
"when you import things from packages, the only implicits possible are singletons" Is it still true with the Scala 2.8 package objects? They could contain implicit defs and vals, too. – Jean-Philippe Pellet Feb 15 '11 at 14:21
  upvote
 flag
@JPP package objects are neither package nor objects -- they are package objects. The objects rule apply for them. – Daniel C. Sobral Feb 15 '11 at 18:10
  upvote
 flag
What I meant is that if you wrote import scala._, you'd import all classes and traits defined in package scala, plus everything in the scala package object, which may contain implicit vals and defs (or am I mistaken?). But of course, the scala package is preimported, this is just an example. – Jean-Philippe Pellet Feb 15 '11 at 19:11
add comment
object ArrayBuffer extends SeqFactory[ArrayBuffer] {
 
/** $genericCanBuildFromInfo */
 
implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, ArrayBuffer[A]] = new GenericCanBuildFrom[A]
 
def newBuilder[A]: Builder[A, ArrayBuffer[A]] = new ArrayBuffer[A]
}
answered Jun 3 at 22:37
Image (Asset 3/3) alt=472
add comment

Your Answer

 
community wiki

Not the answer you're looking for? Browse other questions tagged or ask your own question.