Where does Scala look for implicits?
Solution 1
Types of Implicits
Implicits in Scala refers to either a value that can be passed "automatically", so to speak, or a conversion from one type to another that is made automatically.
Implicit Conversion
Speaking very briefly about the latter type, if one calls a method m
on an object o
of a class C
, and that class does not support method m
, then Scala will look for an implicit conversion from C
to something that does support m
. A simple example would be the method map
on String
:
"abc".map(_.toInt)
String
does not support the method map
, but StringOps
does, and there's an implicit conversion from String
to StringOps
available (see implicit def augmentString
on Predef
).
Implicit Parameters
The other kind of implicit is the implicit parameter. These are passed to method calls like any other parameter, but the compiler tries to fill them in automatically. If it can't, it will complain. One can pass these parameters explicitly, which is how one uses breakOut
, for example (see question about breakOut
, on a day you are feeling up for a challenge).
In this case, one has to declare the need for an implicit, such as the foo
method declaration:
def foo[T](t: T)(implicit integral: Integral[T]) {println(integral)}
View Bounds
There's one situation where an implicit is both an implicit conversion and an implicit parameter. For example:
def getIndex[T, CC](seq: CC, value: T)(implicit conv: CC => Seq[T]) = seq.indexOf(value)
getIndex("abc", 'a')
The method getIndex
can receive any object, as long as there is an implicit conversion available from its class to Seq[T]
. Because of that, I can pass a String
to getIndex
, and it will work.
Behind the scenes, the compiler changes seq.IndexOf(value)
to conv(seq).indexOf(value)
.
This is so useful that there is syntactic sugar to write them. Using this syntactic sugar, getIndex
can be defined like this:
def getIndex[T, CC <% Seq[T]](seq: CC, value: T) = seq.indexOf(value)
This syntactic sugar is described as a view bound, akin to an upper bound (CC <: Seq[Int]
) or a lower bound (T >: Null
).
Context Bounds
Another common pattern in implicit parameters is the type class pattern. This pattern enables the provision of common interfaces to classes which did not declare them. It can both serve as a bridge pattern -- gaining separation of concerns -- and as an adapter pattern.
The Integral
class you mentioned is a classic example of type class pattern. Another example on Scala's standard library is Ordering
. There's a library that makes heavy use of this pattern, called Scalaz.
This is an example of its use:
def sum[T](list: List[T])(implicit integral: Integral[T]): T = {
import integral._ // get the implicits in question into scope
list.foldLeft(integral.zero)(_ + _)
}
There is also syntactic sugar for it, called a context bound, which is made less useful by the need to refer to the implicit. A straight conversion of that method looks like this:
def sum[T : Integral](list: List[T]): T = {
val integral = implicitly[Integral[T]]
import integral._ // get the implicits in question into scope
list.foldLeft(integral.zero)(_ + _)
}
Context bounds are more useful when you just need to pass them to other methods that use them. For example, the method sorted
on Seq
needs an implicit Ordering
. To create a method reverseSort
, one could write:
def reverseSort[T : Ordering](seq: Seq[T]) = seq.sorted.reverse
Because Ordering[T]
was implicitly passed to reverseSort
, it can then pass it implicitly to sorted
.
Where do Implicits come from?
When the compiler sees the need for an implicit, either because you are calling a method which does not exist on the object's class, or because you are calling a method that requires an implicit parameter, it will search for an implicit that will fit the need.
This search obey certain rules that define which implicits are visible and which are not. The following table showing where the compiler will search for implicits was taken from an excellent presentation (timestamp 20:20) about implicits by Josh Suereth, which I heartily recommend to anyone wanting to improve their Scala knowledge. It has been complemented since then with feedback and updates.
The implicits available under number 1 below has precedence over the ones under number 2. Other than that, if there are several eligible arguments which match the implicit parameter’s type, a most specific one will be chosen using the rules of static overloading resolution (see Scala Specification §6.26.3). More detailed information can be found in a question I link to at the end of this answer.
- First look in current scope
- Implicits defined in current scope
- Explicit imports
- wildcard imports
Same scope in other files
- Now look at associated types in
- Companion objects of a type
- Implicit scope of an argument's type (2.9.1)
- Implicit scope of type arguments (2.8.0)
- Outer objects for nested types
- Other dimensions
Let's give some examples for them:
Implicits Defined in Current Scope
implicit val n: Int = 5
def add(x: Int)(implicit y: Int) = x + y
add(5) // takes n from the current scope
Explicit Imports
import scala.collection.JavaConversions.mapAsScalaMap
def env = System.getenv() // Java map
val term = env("TERM") // implicit conversion from Java Map to Scala Map
Wildcard Imports
def sum[T : Integral](list: List[T]): T = {
val integral = implicitly[Integral[T]]
import integral._ // get the implicits in question into scope
list.foldLeft(integral.zero)(_ + _)
}
Same Scope in Other Files
Edit: It seems this does not have a different precedence. If you have some example that demonstrates a precedence distinction, please make a comment. Otherwise, don't rely on this one.
This is like the first example, but assuming the implicit definition is in a different file than its usage. See also how package objects might be used in to bring in implicits.
Companion Objects of a Type
There are two object companions of note here. First, the object companion of the "source" type is looked into. For instance, inside the object Option
there is an implicit conversion to Iterable
, so one can call Iterable
methods on Option
, or pass Option
to something expecting an Iterable
. For example:
for {
x <- List(1, 2, 3)
y <- Some('x')
} yield (x, y)
That expression is translated by the compiler to
List(1, 2, 3).flatMap(x => Some('x').map(y => (x, y)))
However, List.flatMap
expects a TraversableOnce
, which Option
is not. The compiler then looks inside Option
's object companion and finds the conversion to Iterable
, which is a TraversableOnce
, making this expression correct.
Second, the companion object of the expected type:
List(1, 2, 3).sorted
The method sorted
takes an implicit Ordering
. In this case, it looks inside the object Ordering
, companion to the class Ordering
, and finds an implicit Ordering[Int]
there.
Note that companion objects of super classes are also looked into. For example:
class A(val n: Int)
object A {
implicit def str(a: A) = "A: %d" format a.n
}
class B(val x: Int, y: Int) extends A(y)
val b = new B(5, 2)
val s: String = b // s == "A: 2"
This is how Scala found the implicit Numeric[Int]
and Numeric[Long]
in your question, by the way, as they are found inside Numeric
, not Integral
.
Implicit Scope of an Argument's Type
If you have a method with an argument type A
, then the implicit scope of type A
will also be considered. By "implicit scope" I mean that all these rules will be applied recursively -- for example, the companion object of A
will be searched for implicits, as per the rule above.
Note that this does not mean the implicit scope of A
will be searched for conversions of that parameter, but of the whole expression. For example:
class A(val n: Int) {
def +(other: A) = new A(n + other.n)
}
object A {
implicit def fromInt(n: Int) = new A(n)
}
// This becomes possible:
1 + new A(1)
// because it is converted into this:
A.fromInt(1) + new A(1)
This is available since Scala 2.9.1.
Implicit Scope of Type Arguments
This is required to make the type class pattern really work. Consider Ordering
, for instance: It comes with some implicits in its companion object, but you can't add stuff to it. So how can you make an Ordering
for your own class that is automatically found?
Let's start with the implementation:
class A(val n: Int)
object A {
implicit val ord = new Ordering[A] {
def compare(x: A, y: A) = implicitly[Ordering[Int]].compare(x.n, y.n)
}
}
So, consider what happens when you call
List(new A(5), new A(2)).sorted
As we saw, the method sorted
expects an Ordering[A]
(actually, it expects an Ordering[B]
, where B >: A
). There isn't any such thing inside Ordering
, and there is no "source" type on which to look. Obviously, it is finding it inside A
, which is a type argument of Ordering
.
This is also how various collection methods expecting CanBuildFrom
work: the implicits are found inside companion objects to the type parameters of CanBuildFrom
.
Note: Ordering
is defined as trait Ordering[T]
, where T
is a type parameter. Previously, I said that Scala looked inside type parameters, which doesn't make much sense. The implicit looked for above is Ordering[A]
, where A
is an actual type, not type parameter: it is a type argument to Ordering
. See section 7.2 of the Scala specification.
This is available since Scala 2.8.0.
Outer Objects for Nested Types
I haven't actually seen examples of this. I'd be grateful if someone could share one. The principle is simple:
class A(val n: Int) {
class B(val m: Int) { require(m < n) }
}
object A {
implicit def bToString(b: A#B) = "B: %d" format b.m
}
val a = new A(5)
val b = new a.B(3)
val s: String = b // s == "B: 3"
Other Dimensions
I'm pretty sure this was a joke, but this answer might not be up-to-date. So don't take this question as being the final arbiter of what is happening, and if you do noticed it has gotten out-of-date, please inform me so that I can fix it.
EDIT
Related questions of interest:
Solution 2
I wanted to find out the precedence of the implicit parameter resolution, not just where it looks for, so I wrote a blog post revisiting implicits without import tax (and implicit parameter precedence again after some feedback).
Here's the list:
- 1) implicits visible to current invocation scope via local declaration, imports, outer scope, inheritance, package object that are accessible without prefix.
- 2) implicit scope, which contains all sort of companion objects and package object that bear some relation to the implicit's type which we search for (i.e. package object of the type, companion object of the type itself, of its type constructor if any, of its parameters if any, and also of its supertype and supertraits).
If at either stage we find more than one implicit, static overloading rule is used to resolve it.
Daniel C. Sobral
I have been programming for more than 20 years now, starting with 8 bits computers, assembler and BASIC. My passion for languages meant that, by the time I entered college, I had already programmed for fun or profit in more than 20 languages, including odd ones like Forth, MUMPS and APL, as well as theoretically important ones like Lisp and Prolog. Some of my code ended up in FreeBSD, of which I was a committer for some years, while I got my masters degree in the field of distributed algorithms. I also contributed to Scala, with small amounts of code, some reasonable amount of documentation, and a couple of years of a lot of attention to the Scala questions on Stack Overflow.
Updated on July 08, 2022Comments
-
Daniel C. Sobral almost 2 years
An implicit question to newcomers to Scala seems to be: where does the compiler look for implicits? I mean implicit because the question never seems to get fully formed, as if there weren't words for it. :-) For example, where do the values for
integral
below come from?scala> import scala.math._ import scala.math._ scala> def foo[T](t: T)(implicit integral: Integral[T]) {println(integral)} foo: [T](t: T)(implicit integral: scala.math.Integral[T])Unit scala> foo(0) scala.math.Numeric$IntIsIntegral$@3dbea611 scala> foo(0L) scala.math.Numeric$LongIsIntegral$@48c610af
Another question that does follow up to those who decide to learn the answer to the first question is how does the compiler choose which implicit to use, in certain situations of apparent ambiguity (but that compile anyway)?
For instance,
scala.Predef
defines two conversions fromString
: one toWrappedString
and another toStringOps
. Both classes, however, share a lot of methods, so why doesn't Scala complain about ambiguity when, say, callingmap
?Note: this question was inspired by this other question, in the hopes of stating the problem in a more general manner. The example was copied from there, because it is referred to in the answer.
-
pedrofurla about 13 yearsIt's time for you to start using your answers in a book, by now it's only a matter of put it all together.
-
Daniel C. Sobral about 13 years@pedrofurla I have been considered writing a book in portuguese. If someone can find me a contact with a technical publisher...
-
pedrofurla about 13 years@Daniel, I know. And I also volunteered to review it :)
-
retronym about 13 yearsThe package objects of the companions of the parts of the type are also searched. lampsvn.epfl.ch/trac/scala/ticket/4427
-
Daniel C. Sobral about 13 years@retronym IMHO, things defined in the package object are "current scope" for other stuff in the package, so they'd be handled either as current scope in the same file or as same scope, different file, as the case may be.
-
retronym about 13 yearsIn this case, it's part of the implicit scope. The call site need not be within that package. That was surprising to me.
-
Kipton Barros almost 13 yearsNice list of sources for implicits. How is ambiguity resolved? You listed 8 sources (1.1, 1.2, ... 2.4). Are implicits shadowed in this order, with 1.1 taking highest priority?
-
Daniel C. Sobral almost 13 years@Kipton 7, actually. They 8th is a joke. Yes, these source are ordered by priority. Within a category, there's ambiguity, except in the case of inheritance. An inherited implicit has lower precedence than one not inherited.
-
retronym over 12 yearsOne more place to look: stackoverflow.com/questions/7647835/…
-
Daniel C. Sobral over 12 years@retronym Thank you, I missed that one! Updated.
-
Daniel C. Sobral over 12 yearsThis could be improved if you wrote some code just defining packages, objects, traits and classes, and using their letters when you refer to the scope. No need to put any method declaration at all -- just names and who extends whom, and in which scope.
-
Eugene Yokota over 12 yearsThe current scope also includes implicit parameters of the current method, outer blocks, inherited implicits, and implicits made available by package object. The only precedence among the current scope is locally defined one vs the rest in 2.9.1, but it's a bug. After 2.10, all of them within current scope have the same precedence. The same goes for implicit scope. When there are more than one candidate, static overloading rule is used, which means the implicits defined in an object wins over implicits defined in its supertrait etc.
-
Daniel C. Sobral over 12 years@EugeneYokota I'd rather "outsource" the whole issue of implicit resolution precedence. Would you mind asking/answering that question? You have tons of material already from your blog. :-) Also, it would be a nice additions to the FAQ at the doc site.
-
Eugene Yokota over 12 yearsYea, so stackoverflow.com/questions/8623055 covers that specifically, but I noticed you wrote "The following list is intended to be presented in precedence order ... please report." Basically, the inner lists should be unordered since they all have equal weight (at least in 2.10).
-
lcn about 10 years@DanielC.Sobral, I found the "Second, the companion object of the expected type" saying very misleading. Both Joshua Suereth (on page 102 of Scala in Depth) and Martin Odersky (eed3si9n.com/…) say the search happens only for the source type. In the example you gave, List(1, 2, 3).sorted, the search of an Ordering[T] has nothing to do with expected type. The Ordering[T] here is just a comparator, which is a function.
-
Daniel C. Sobral about 10 years@lcn Your last sentence is irrelevant -- comparator and function have nothing to do with it. It needs an implicit of type
Ordering[T]
. Where should it look for it, and why? There's no method being called on an object of the typeOrdering[T]
, so source type does not apply. Explain from there. -
lcn about 10 years@DanielC.Sobral, Yes, I shall have limited my previous comment to implicit conversions when talking about the search. Yet as for implicit parameters, which your List.ordered example falls into, there is neither a source type nor an expected type. Though the " implicit object Int extends IntOrdering" is defined in the "Ordering" object, the search for such an implicit is not initiated by an expected type, even though Ordering serves here as the expected type of Int. So using it as an example for illustrating search in "the companion object of the expected type" is still inappropriate.
-
Daniel C. Sobral about 10 years@lcn If you cannot provide an explanation of how
IntOrdering
insideobject Ordering
is found, then you must assume you are wrong. Not me, you must assume so. As it happens, the sources you cite contradict you. Odersky said we look in the "implicit scope", which contains all sort of companion objects that bear some relation to the type which we search for -- "type which we search for" is the expected type. Josh says on 5.1.3 "implicit scope of the type it's looking for" -- again, expected type. Or consider this commit's second paragraph. -
lcn about 10 years@DanielC.Sobral, I guess our disagreement is about the concept "expected type". To locate the implicit definition of an implicit parameter, the compiler does have to find in the companion object of that parameter's type, which does be an expected type. But this situation has to be distinguished from the case for implicit conversion, "implicit def int2bigInt(i: Int): BigInt", which is defined in the BigInt companian object instead of in Int object, the source type. This in my opinion is the real case for implicit search in an expected type.
-
Daniel C. Sobral about 10 years@lcn There's no need to distinguish between these cases, because they are the same wrt to where the implicit is found.
-
Paul Draper over 9 yearsYour
1 + new A(1)
example does not work. (2.11.4): "overloaded method value + with alternatives...cannot be applied to (A)" -
Daniel C. Sobral over 9 years@PaulDraper I just tested on 2.11.4, and it worked. It also certainly worked back on whatever version I original used at the time I wrote this. What version are you using, and are you sure you don't have other implicits defined? These examples are not supposed to be used together, for one thing.
-
ievgen.garkusha over 7 yearsanother simple example for "outer objects for nested types": objectOuter{ trait Nested implicit val i: Nested = new Nested{} } implicitly[Outer.Nested]
-
metasim about 7 yearsUnfortunately, the link to @jsuereth 's presentation is now blocked.
-
dade about 7 yearsThe
1 + new A(1)
seems to work for the wrong reason. I changed+
to+++
and expected it to work: ` class A(val n: Int) { def +++(other: A) = new A(n + other.n) } object A { implicit def fromInt(n: Int) = new A(n) } ` but got this: ` // This becomes possible: 1.+++(new A(1)) // compile error A.fromInt(1) +++ new A(1) // this works ` -
steinybot over 6 years"Same Scope in Other Files" is a little unclear. I expected package objects from parent packages of the current scope to be searched but they are not. It is actually the package objects for the type that is searched. @retronym hints at this.
x.implicitFoo
will only search the scope ofx
and not the scope of where it is used. (see gist for an example)[gist.github.com/steinybot/121d24730edda4d815918c08b7d64a46] -
Julian A. over 4 years@DanielC.Sobral Can you explain more what you mean by “ this does not mean the implicit scope of A will be searched for conversions of that parameter, but of the whole expression”? What is the “whole expression”? Thanks.
-
Daniel C. Sobral over 4 years@JulianA. See the example that follows:
1 + new A(1)
. Here, the+
method on theA
class takes andA
, so there's no implicit conversion happening for the parameter itself, but because the parameter is of typeA
, then the implicit scope forA
is applied to other elements of the expression, once the initial look up fails, which is why the object on which the+
method is called gets an implicit conversion. -
soMuchToLearnAndShare over 3 yearsWhere does implicit class fit into the types you mentioned here? The scala doc did not say much, only says “make” the primary constructor available for type conversion , but didn’t give examples . docs.scala-lang.org/overviews/core/implicit-classes.html
-
Daniel C. Sobral over 3 years@soMuchToLearn It doesn't. They didn't exist at the time, and since they are being replaced on Scala 3 I'm not sure it's worth adding them to the answer, though I would not object if someone else edited the answer to add them.
-
mert inan over 2 yearsI had to vote this up