Introduction

Not long ago I stumbled upon the signature of the flatten method on Option:

def flatten[B](implicit ev: A <:< Option[B]): Option[B]

I don’t know about you, but I knew about implicit parameter lists, implicit resolution, and even type bounds. But this funny <:< “sad-with-a-hat” [1] operator [2] was entirely new to me!

Smart people [3] have written about it years ago, but it’s clear that we are talking about a feature which is not well-known and poorly documented, even though it is available since Scala 2.8. So this article is about figuring out what it means and how it works.

The following deconstruction turns out to be fairly long, but even though <:< itself may not be useful to every Scala programmer, it touches a surprisingly large number of Scala features which most Scala programmers should know.

What it does and how it’s useful

If you search the Scala standard library, you find a few other occurrences of <:<, in particular:

• on Option:

  def orNull[A1 >: A](implicit ev: Null <:< A1): A1

• on Traversable (via traits like GenTraversableOnce):

  def toMap[K, V](implicit ev: A <:< (K, V)): Map[K, V]

• on Either:

  def joinRight[A1 >: A, B1 >: B, C](implicit ev: B1 <:< Either[A1, C]): Either[A1, C]

• on Try:

  def flatten[U](implicit ev: T <:< Try[U]): Try[U]

You notice that, in all these examples, <:< is used in the same way:

• there is an implicit parameter list, with a single parameter called ev
• the type of this parameter is of the form Type1 <:< Type2

The lowdown is that this pattern tells the compiler:

Make sure that Type1 is a subtype of Type2, or else report an error.

This is part of a feature called generalized type constraints. [4] There is another similar construct, =:=, which tells the compiler: [5]

Make sure that Type1 is exactly the same as Type2, or else report an error.

In what follows, I am focusing on <:< which turns out to be more useful, but just know that =:= is a thing and works in a very similar way.

The why and how of this feature is the subject of the rest of this article! So for now, let’s take this as a recipe, a trick if you will, while we look at how this can be useful in practice.

Let’s start with flatten on Option:

def flatten[B](implicit ev: A <:< Option[B]): Option[B]

What does flatten do, as per the documentation? It removes a level of nesting of options:

scala> val oo: Option[Option[Int]] = Some(Some(42))
oo: Option[Option[Int]] = Some(Some(42))

scala> oo.flatten
res1: Option[Int] = Some(42)

This doesn’t make much sense if the type parameter A of Option is not, itself, an Option-of-something. So what should happen if you call flatten on, say, an Option[String]? I see two possibilities:

1. The flatten method returns None.
2. The compiler reports an error.

The authors of the Scala standard library picked option 2, and I think that it’s a good choice, because most likely calling flatten in this case is not what the programmer intends. And lo and behold, the compiler doesn’t let this pass:

scala> val oi: Option[Int] = Some(42)
oi: Option[Int] = Some(42)

scala> oi.flatten
<console>:21: error: Cannot prove that Int <:< Option[B].
       oi.flatten

So we have a generic type, Option[+A], which has a method, flatten, which can only be used if the type parameter A is itself an Option. All the other methods (except orNull which is similar to flatten) can be called: map, get, etc. But flatten? Only if the type of the option is right!

One thing to realize is that we have something unusual here: a method which the compiler won’t let us call, not because we pass incorrect parameters to the method (in fact flatten doesn’t even take any explicit parameters), but based on the value of a type parameter of the underlying Option class. This is not something you see in Java, and you have probably rarely seen it in Scala.

Looking again at the signature of flatten, we can see how the recipe is applied: implicit ev: A <:< Option[B] reads “make sure that A is a subtype of Option[B]”, and, since A stands for the parameter type of Option, we have:

• in the first case “make sure that Option[Int] is a subtype of Option[B]”
• in the second case “make sure that Int is a subtype of Option[B]”

Obviously, Option[Int] can be a subtype of an Option[B], where B = Int (or B = AnyVal, or B = Any). On the flip side, there is just no way Int can be a subtype of Option[B], whatever B might be. So the recipe works, and therefore the constraint works. [6]

To get the hang of it, let’s look at another nice use case , toMap on Traversable:

def toMap[K, V](implicit ev: A <:< (K, V)): Map[K, V]

Translated into English: you can convert a Traversable to a Map with toMap, but only if the element type is a tuple (K, V). This makes sense, because a Map can be seen as a collection of key/value tuples. It wouldn’t make great sense to create a Map just out of a sequence of 5 Ints, for example.

Similar rationales apply to the few other uses of <:< in the standard library, which all come down to constraining methods to work with a specific contained type only.

In light of these examples, I find that applying this recipe is easy, even though the syntax is a bit funny. But I can think of a few questions:

1. Can’t we just use type bounds which I thought existed to enforce this kind of type constraints?
2. If this is a pattern rather than a built-in feature, why does <:< look so much like an operator? Does the compiler have special support for it?
3. How does this whole thing even work?
4. Is there an easier ways to achieve the same result?

Let’s look into each of these questions in order.

Question 1: Can’t we just use type bounds?

Lower and upper bounds

Type bounds cover lower bounds and upper bounds. [7] These are well explained in the book Programming in Scala, so I won’t cover the basics here, but I will present some perspective on how they work.

As a reminder, lower and upper bounds are expressed with builtin syntax: >: and <: (spec). You can read:

• T >: U as “type T is a supertype of type U” or “type T has type U as lower bound”
• T <: U as “type T is a subtype of type U” or “type T has type U as upper bound”

A puzzler

Let’s consider the following:

scala> def tuple[T, U](t: T, u: U) = (t, u)
tuple: [T, U](t: T, u: U)(T, U)

My tuple function simply returns a tuple of the two values passed, whatever their types might be. Granted, it’s not very useful!

What are T and U? They are type variables: they stand for actual types that will be decided at each call site (each use of the function in the source code). Here both T and U are abstract: we don’t know what they will be when we write the function. For example we don’t say that U is a Banana, which would be a concrete type.

If we pass String and Int parameters, we get back a tuple (String, Int) in the Scala REPL:

scala> tuple("Lincoln", 42)
res1: (String, Int) = (Lincoln,42)

Now let’s consider the following modification, which is a naive attempt at enforcing type constraints with type bounds:

def tupleIfSubtype[T <: U, U](t: T, u: U) = (t, u)

I know, it’s starting to be like an alphabet (and symbol) soup! But let’s stay calm: the only change is that instead of specifying just T as type parameter, we specify T <: U, which means “T must be a subtype of U”.

The intent of tupleIfSubtype is to return a tuple of the two values passed, like tuple above, but fail at compile time if the first value is not a subtype of the second value.

So does the newly added constraint work? Do you think that the compiler will accept to compile this?

tupleIfSubtype("Lincoln", 42)

Before knowing better, I would have thought that the compiler:

• would decide that T = String
• would decide that U = Int
• see the type constraint T <: U, which translates into String <: Int
• fail compilation because obviously, String is not a subtype of Int

But it turns out that this actually compiles just fine!

How can this be? Is the constraint not considered? Is it a bug in the compiler? A weird edge case? Bad language design? Or maybe, with T <: U, the U is not the same as the second U in the type parameter section? This can quickly be proven false:

scala> def tupleIfSubtype[T <: V, U](t: T, u: U) = (t, u)
<console>:7: error: not found: type V
       def tupleIfSubtype[T <: V, U](t: T, u: U) = (t, u)

So the two Us are, as seemed to make sense intuitively, bound to each other (they refer to the same type).

The answer to this puzzler turns out to be relatively simple: it has to do with the way type inference works, namely that type inference solves a constraint system (spec).

What happens is that yes, I do pass String and Int, but it doesn’t follow that T = String and U = Int. Instead, the effective T and U are the result of the compiler working its type inference algorithm, given:

• the types of the parameters we actually pass to the function,
• the constraints expressed in the type parameter section,
• and, in some cases, the expression’s return type.

If I write:

scala> def tuple[T, U](t: T, u: U) = (t, u)
tuple: [T, U](t: T, u: U)(T, U)

scala> tuple("Lincoln", 42)
res3: (String, Int) = (Lincoln,42)

then yes: T = String and U = Int because there are no other constraints. But when I introduce an upper bound, there is a constraint, and therefore a constraint system. The compiler resolves it and obtains T = String and U = Any:

scala> def tupleIfSubtype[T <: U, U](t: T, u: U) = (t, u)
tupleIfSubtype: [T <: U, U](t: T, u: U)(T, U)

scala> tupleIfSubtype("Lincoln", 42)
res4: (String, Any) = (Lincoln,42)

We can verify that the resulting types satisfy the constraints: [8]

• String is a String of course
• Int is a subtype of Any
• String is also a subtype of Any

Phew! So this makes sense. It’s “just” a matter of understanding how type inference works when type bounds are present.

In the process we have learned that <: and >:, when used with abstract type parameters, do not necessarily produce results which are very useful, because the compiler can easily infer Any (or AnyVal or AnyRef) as solutions to the constraint system. [9]

Question 2: Why does <:< look so much like an operator?

Lets dig a little deeper to understand how <:< works under the hood. Here is a simple type hierarchy used in the examples below:

trait Fruit
class Apple  extends Fruit
class Banana extends Fruit

Parameter lists and type inference

Let’s start with a couple more things you need to know in Scala:

• Functions can have more than one parameter list.
• Type inference operates parameter list per parameter list from left to right.

In particular, an implicit parameter list can use types inferred in previous parameter lists.

So let’s write the solution, without necessarily understanding it fully yet:

def tupleIfSubtype[T, U](t: T, u: U)(implicit ev: T <:< U) = (t, u)

This function has two parameter lists:

• (t: T, u: U)
• (implicit ev: T <:< U)

Because type inference goes parameter list by parameter list, let’s start with the first one. You notice that there are no >: or <: type bounds! So:

• T is whatever specific type t has (say T = Banana)
• U is whatever specific type u has (say U = Fruit)

Infix types

Looking at the second parameter list, we have to clear a hurdle: what kind of syntax is T <:< U? This notation is called an infix type (spec). “Infix” just means that a type appears in the middle of two other types, the same way the + operator appears in the middle in 2 + 2. The type in the middle (the infix type proper) can be referred to a an infix operator. Instead of this operator being a method, as is the case in general in Scala, it is a type.

Let’s look at examples. You probably know types from the standard library such as:

Map[String, Fruit]
Either[String, Boolean]

These exact same types can be written:

String Map Fruit
String Either Boolean

The infix notation makes the parametrized type look like an operator, but an operator on types instead of values. Other than that, it’s just an alternate syntax, and really nothing to worry about!

So based on the above:

T <:< U

means the the same as:

<:<[T, U]

A symbolic type name

Now, what is a <:<? It’s a type: the same kind of stuff as Map or Either, in other words, typically a class or a trait. It’s just that this is a symbolic name instead of an alphabetic identifier like Map. It could as well have been called SubtypeOf, and maybe it should have been!

The implicit parameter

So once we reach the second (and implicit) parameter list:

(implicit ev: T <:< U)

we see that there is a parameter of type <:<, which itself has two type parameters, T and U. These are the same T and U we have in the first parameter list. They are bound to those, and these are known because type inference already did its magic on the first parameter list. Concretely, T is now assigned the type Banana and U the type Fruit!

What the implicit parameter list says is this: “Find me, somewhere in the implicit search path, an implicit val, def, or class of type <:< which satisfies <:<[T, U]”. [10] And because T and U are now known, we need to find an implicit match for <:<[Banana, Fruit].

The trick is to manage to have an implicit definition in scope which matches only if there is a subtype relationship between T and U. For example:

T	U	Compiler Happiness Level
Banana	Fruit	happy
Apple	Fruit	happy
Int	Anyval	happy
Apple	Banana	unhappy
String	Int	unhappy

If we manage to create such an implicit definition, the constraint mechanism works. And we already know that the clever engineers who devised this have found a way to create such an implicit definition!

By the way, we can play with this in the REPL using the standard implicitly function, which returns an implicit value for the given type parameter if one is found:

implicitly[Banana <:< Fruit]  // ok
implicitly[Apple  <:< Fruit]  // ok
implicitly[Int    <:< Anyval] // ok
implicitly[Apple  <:< Banana] // not ok
implicitly[String <:< Int]    // not ok

To summarize, we now have a pretty good level of understanding and we know that:

• we are talking about a library feature
• which relies on an implicit parameter
• with a funny symbolic type operator <:<.

And we also know that the magic that makes it all work lies in the search for a matching implicit definition: if it is found, the subtyping relationship holds, otherwise it doesn’t and the compiler reports and error.

Question 3: How does this whole thing even work?

We could stop here and be happy to use <:< like a recipe, as if it was a core language feature. But that wouldn’t be very satisfying, would it? After all, we still miss the deeper understanding of how that magic implicit is defined, and why an implicit search for it may or may not match it. So let’s keep going!

The implementation

Let’s look at the implementation of <:<, which we find in the Scala Predef object [11]:

@implicitNotFound(msg = "Cannot prove that ${From} <:< ${To}.")
sealed abstract class <:<[-From, +To] extends (From ⇒ To) with Serializable

private[this] final val singleton_<:< = new <:<[Any, Any] {
  def apply(x: Any): Any = x
}

implicit def $conforms[A]: A <:< A = singleton_<:<.asInstanceOf[A <:< A]

Wow! Can we figure it out? Let’s try.

Which implicit?

Let’s think about a simpler case of implicit search:

def makeMeASandwich(implicit logger: Logger) = ...

implicit def findMyLogger: Logger = ...

val mySandwich = makeMeASandwich

The compiler, when you write makeMeASandwich without an explicit parameter, looks for an implicit in scope of type Logger. Here, the obvious matching implicit is findMyLogger, because it returns a Logger. So the compiler selects the implicit and in effect rewrites your code as:

val mySandwich = makeMeASandwich(findMyLogger)

The same mechanism is at work with implicit ev: T <:< U: the compiler must find an implicit of type T <:< U (or <:<[T, U] which is exactly the same). And there is only one implicit definition with type <:<-of-something in the whole standard library, which is:

implicit def $conforms[A]: A <:< A

Now there is a bit of a twist, because the implicit is of type <:<[A, A], with a single type parameter A, which in addition is abstract. [12] Anyhow, this means that our function parameter ev of type <:<[T, U] must, somehow, “match” with <:<[A, A].

If we ask ourselves: what does it take for this implicit of type <:<[A, A] to be successfully selected by the compiler? The answer is that one should be able, for some type A to be determined, to pass a value of type <:<[A, A] to the parameter of type <:<[T, U]. Another way to say this is that <:<[A, A] must conform to <:<[T, U]. If we can’t do this, the implicit search will fail.

Variance

How does this conformance work? This takes us to the notion of variance, which is always a fun thing. Consider a Scala immutable Seq. It is defined as trait Seq[+A]. The little + says that if I require a Seq[Fruit], I can pass a Seq[Banana] just fine:

def takeFruits(fruits: Seq[Fruit]) = ...
takeFruits(Seq(new Banana))

This is called covariance (the subtyping of the type argument goes in the same direction as the enclosing type). Without the notion of covariance and contravariance (where subtyping of the type argument goes in the opposite direction as the enclosing type), you:

• either can never write code like this (everything is invariant)
• or you have an unsound type system [13]

Besides collections, functions are another example where variance and contravariance matter. Say the following process function expects a single parameter, which is a function of one argument:

def process(f: Banana ⇒ Fruit)

I can of course pass to process a function with these exact same types:

def f1(f: Banana): Fruit = f
process(f1)

But Scala’s support for subtyping also applies to functions: a function can be a subtype of another function. So I can pass a function with types different from Banana and Fruit without breaking expectations as long as the function:

• takes a parameter which is a supertype of Banana
• returns a value of a subtype of Fruit

For example:

def f2(f: Fruit): Apple = new Apple
process(f2)

This is the magic of variance, and you can convince yourself that it makes sense from the point of view of the process function: expectations won’t be violated.

Functions are not a special case in Scala from this point of view: a function of one parameter is defined (in a simplified version) as a trait with the function parameter as contravariant and the result as covariant:

trait Function1[-From, +To] { def apply(from: From): To }

Putting everything together

After this detour in variance land, let’s get back to <:< and the implicit parameter. The implicit <:<[A, A] will conform to the parameter <:<[T, U] if it follows the variance rules. So what’s the variance on <:<[T, U] in Predef?

<:<[-From, +To]

This is the same as Function1[-From, +To] and in fact <:< extends Function1! So our problem comes down to the following question: if somebody requires a function:

T ⇒ U

what constraints must be satisfied so I can pass the following function:

A ⇒ A

With variance rules, we know it will work if:

• A is supertype of T
• and A is subtype of U

Written in terms of bounds:

T <: A <: U

Which means of course that T <: U: T must be a subtype of U!

To summarize the reasoning: the only eligible implicit definition in scope which can possibly be selected by the compiler to pass to our function is selected if and only if T is a subtype of U! And that’s exactly what we were looking for! [14]

You can look at this from a slightly more general angle, which is that a function A ⇒ A can only be passed to a function T ⇒ U if T is a subtype of U. [15] You can in fact test the matching logic very simply with the built-in identity function:

val f: Banana ⇒ Fruit  = identity // ok
val f: Fruit  ⇒ Banana = identity // not ok

The same works with $conforms, which returns an <:<, which is also an identity function:

val f: Banana ⇒ Fruit  = $conforms // ok
val f: Fruit  ⇒ Banana = $conforms // not ok

So it is a neat trick that the library authors [16] pulled off here, combining implicits and conformance of function types to implement constraint checking.

The nitty-gritty

The rest of the related code in Predef is about defining the actual <:< type and creating a singleton instance returned by def $conforms[A], because in case the implicit search matches, it must return a real value after all.

You could write it minimally (using <::< in these attempts so as to not clash with the standard <:<):

sealed trait <::<[-From <: To, +To] extends (From ⇒ To) {
  def apply(x: From): To = x
}

implicit def $conforms[A]: A <::< A =
    new <::<[A, A] {}

But oops, the compiler complains:

scala> def tupleIfSubtype[T, U](t: T, u: U)(implicit ev: T <::< U) = (t, u)
<console>:23: error: type arguments [T,U] do not conform to trait <::<'s type parameter bounds [-From <: To,+To]
       def tupleIfSubtype[T, U](t: T, u: U)(implicit ev: T <::< U) = (t, u)

The good news is that the following version, using an intermediate class, works:

sealed trait <::<[-From, +To] extends (From ⇒ To)

final class $conformance[A] extends <::<[A, A] {
  def apply(x: A): A = x
}

implicit def $conforms[A]: A <::< A =
  new $conformance[A]

So this works great, with a caveat: every time you use my version of <::<, a new instance of the anonymous class is created. Since we just want an identity function, which works the same for all types and doesn’t hold state, it would be good to use a singleton so as to avoid unnecessary allocations. We could try using an object, since that’s how we do singletons in Scala, but that’s a dead-end because objects cannot take type parameters:

scala> implicit object Conforms[A] extends (A ⇒ A) { def apply(x: A): A = x }
<console>:1: error: ';' expected but '[' found.
implicit object Conforms[A] extends (A ⇒ A) { def apply(x: A): A = x }

So in the end the standard implementation cheats by creating an untyped singleton using Any, and casting to [A <:< A] in the implementation of $conforms. Here is my attempt, which works fine:

private[this] final object Singleton_<::< extends <::<[Any, Any] {
  def apply(x: Any): Any = x
}

implicit def $conforms[A]: A <::< A =
    Singleton_<::<.asInstanceOf[A <::< A]

The actual Scala implementation opts for using a val instead of an object (maybe to avoid the cost associated with an object’s lazy initialization):

private[this] final val singleton_<:< = new <:<[Any, Any] {
  def apply(x: Any): Any = x
}

implicit def $conforms[A]: A <:< A =
    singleton_<:<.asInstanceOf[A <:< A]

We are only missing one last bit:

@implicitNotFound(msg = "Cannot prove that ${From} <:< ${To}.")
sealed abstract class <:<[-From, +To] ...

This helps provide the user with a nice message when the implicit is not found. From a syntax perspective, it is a regular annotation, which applies to the abstract class <:<. The annotation is known by the compiler. [17]

So here we are: the implementation is explained! It’s a bit trickier than it should be in order to prevent extra allocations. I confess that I am a bit disappointed that there doesn’t seem to be a way to avoid an instanceOf: even though it’s local to the implementation and therefore the lack of safety remains under control, it would be better if it could be avoided.

An implicit conversion

One thing you might wonder is what to do with the ev parameter. After all, a value must be passed to the function when the implicit is found (when it’s not found, the compiler blows up so ev doesn’t need an actual value).

A first answer is that you don’t absolutely need to use it. It’s there first so the compiler can check the constraint. That’s why it’s commonly called ev, for “evidence”: its presence stands there as a proof that something (an implicit) exists.

Nonetheless, ev must have a value. What is it? It’s the result of the $conforms[A] function, which is of course of type <:<[T, U]. And we have seen above that <:< extends T ⇒ U. So the result of $conforms[A] is a function, which takes an A and returns an A, that is, an identity function. And it not only returns a value of the same type A, but it actually returns the same value which was passed (that’s the idea of an identity function).

And you see that in the implementation:

def apply(x: Any): Any = x

It follows that ev has for value an identity function from T to U: it takes a value t of type T and returns that same value but with type U. This is possible, and makes sense, as we know that T is a subtype of U, otherwise the implicit wouldn’t have been found.

But there is more: ev is also an implicit conversion from T to U (from Banana to Fruit). How so? Because it has the keyword implicit in front of it, that’s why!

To contrast with regular type bounds, if you write:

def tupleIfSubtype[T <: U, U](t: T, u: U) = ...

the compiler knows that T is a subtype of U, thanks of the native semantic of <:. But with <:<, the compiler knows nothing of the sort based on the type parameter section.

However the presence of the implicit ev function makes it possible to use the value t of type T as a value of type U. The subtype relationship can be seen as an implicit conversion. This is much safer than using t.asInstanceOf[U]. You could also be extra-explicit and write:

ev(t)

So you can write:

def tToU[T, U](t: T, u: U)(implicit ev: T <:< U): U = t

or:

def tToU[T, U](t: T, u: U)(implicit ev: T <:< U): U = ev(t)

Without the implicit conversion, the compiler complains:

scala> def tToU[T, U](t: T, u: U): U = t
<console>:10: error: type mismatch;
 found   : t.type (with underlying type T)
 required: U
       def tToU[T, U](t: T, u: U): U = t

You can see how Option.flatten makes use of the ev() function:

def flatten[B](implicit ev: A <:< Option[B]): Option[B] =
  if (isEmpty) None else ev(this.get)

In summary, all these features fall together to produce something that makes a lot of sense and is useful.

Question 4: Is there an easier ways to achieve the same result?

There is at least one other way something like what <:< does can be achieved. The idea is that a method such as flatten does not need to be included on the base class or trait, in this case Option. Instead, Scala has, via implicit conversions, what in effect achieves extension methods (AKA the “extend my library” pattern).

So say that such an extension method is only available on values of type Option[Option[T]]:

implicit class OptionOption[T](val oo: Option[Option[T]]) extends AnyVal {
  def flattenMe: Option[T] = oo flatMap identity
}

If we try to apply it to Some(Some(42)), the method is found and the flattening works:

scala> Some(Some(42)).flattenMe
res0: Option[Int] = Some(42)

If we try to apply it to Some(42), the method is not found and the compiler reports an error:

scala> Some(42).flattenMe
<console>:13: error: value flattenMe is not a member of Some[Int]
       Some(42).flattenMe

But I see a few differences with the <:< operator:

• You need to create one implicit class for each type supporting a conversion. In the case of Option, for example, you need one implicit class taking an Option[Option[T] to support flatten, and another implicit class to support orNull. So this requires a bit more boilerplate than <:< per method.
• I am not sure whether there something similar to @implicitNotFound to report a better error in case of problem.

So why not do it this way? I think that a good case can be made that it is easier to understand in the case of the relatively simple examples we have seen so far.

UPDATE 2015–12–10: Somebody kindly pointed out that at the time generalized type constraints were implemented, Scala didn’t yet have value classes or implicit classes. Missing value classes meant boxing overhead when running extension methods, while missing implicit classes just meant more boilerplate. So using an implicit value class as I did above was not a great option at the time.

On the other hand, <:< is a more flexible library feature which you can reuse easily and even combine with other implicits, like in this example using Shapeless: [18]

def makeJava[F, A, L, S, R](f: F)(implicit
  ftp: FnToProduct.Aux[F, L => S],
  ev: S <:< Seq[R],
  ffp: FnFromProduct[L => JList[R]]
)

Finally, when using type bounds, the constraints expressed with <: and >: can only apply to the method type parameters (or class type parameters when they are used on a class). This is very useful, as we have seen. But when using <:<, you can constrain any two types in scope, and even impose multiple such constraints. Your imagination is the limit:

trait T[A, B] {

  type C
  type D

  def constrainTwoTraitParams         (implicit ev: A <:< B) = ()
  def constrainTraitParamAndTypeMember(implicit ev: A <:< C) = ()
  def constrainTwoTypeMembers         (implicit ev: C <:< D) = ()
  def constrainMore[Y](c: Y)          (implicit ev1: A <:< B, ev2: Y <:< C) = ()
}

class C extends T[Banana, Fruit] {
  type U = Fruit
  type V = String
}

You can even go further and constrain not only these types directly, but higher-order types, as in this (math- and symbol-heavy) example from Miles Sabin:

def size[T](t: T)(implicit ev: (¬¬[T] <:< (Int ∨ String))) = ???

In this case, the constraint is not directly on the T type parameter, but on ¬¬[T].

This might be, after all, how the term “generalized type constraint” gets its name.

Perspectives

We have seen how regular type bounds:

• behave when using abstract type parameters
• but don’t work to actually enforce certain useful constraints.

We have also seen how we can use instead a generalized type constraint expressed with <:<:

• to implement methods which can only be used when types are aligned in a certain way
• and how <:< is not a built-in feature of the compiler, but instead a library feature implemented via a smart trick involving implicit search and type conformance.

Finally, we have considered:

• how the simple use cases in the standard library could be implemented differently
• but also how <:< is a more general tool.

So is <:< is worth it? Should it be part of the standard library, and should Scala developers learn it?

I think that the feature suffers from the fact that is is not properly documented, explained, and put in perspective. It also suffers from being a symbolic name with no agreed upon way to pronounce it!

The standard library uses of <:< could be replaced with “extension methods”, which would achieve the same result via Scala features which are easier to understand and familiar to most Scala programmers. I think that this argues against the presence of <:< in the standard library, especially at the level of Predef, and if this was introduced today, my inclination would be to recommend leaving it to third-party libraries such as Shapeless which actually benefit the most from this kind of advanced features.

On the plus side, when used <:< as a recipe, it is easy to understand and useful, and I can’t help but being impressed that generalized type constraints are implemented at the library level, and that they can emerge from powerful underlying language features such as type inference and implicits.

This is typical of Scala, and in line with the principle of Martin Odersky that it is better to keep the core language small when possible. So even though the explanation of how <:< works might seem a bit tricky, you can take comfort in thinking that in other languages this might be compiler code, not library code. But I also understand how some programmers [19] might be bothered by all the machinery behind features like this.

As for me, I am keeping generalized type constraints in my toolbox, but I like seeing the feature as a gateway to a more in-depth understanding of Scala. I hope this post will help others along this path as well!

Did I get anything wrong? Please let me know!

What it is

I am not a language designer but I love programming languages, so I can’t resist putting down a few rough thought on Swift, the new programming language announced on Monday by Apple. It is designed to make Objective-C, the main language used to build apps on iOS and OS X, a thing of the past. I think it’s fair to say that this was, for developers, the highlight of Monday’s WWDC keynote.

Objective-C is a dinosaur language, invented in the early 1980s. If you know any relatively more modern higher-level language (pick one, including C#, Scala, even Hack), it is clear that it has too much historical baggage and not enough of the features programmers expect.

John Siracusa captured the general idea in his 2005 Avoiding Copland 2010 article and its revision, Copland 2010 revisited: Apple’s language and API future, and has kept building a really good case since, in various podcasts, that Apple had to get their act together. Something, anything, had to be done. [1]

There was a possibility that Apple would keep patching Objective-C, moving toward a superset of a safe subset of it. But I don’t think that anybody not working at Apple saw Swift coming that, well, swiftly. [2]

Why this is good for programmers

Reactions to Swift so far seem mostly positive. (I don’t tend to take the negative reactions I have seen seriously as they are not argumented.) As Jeff Atwood tweeted: “TIL nobody actually liked Objective-C.”. I share the positive feeling for three reasons:

First, I believe that programming languages matter:

• they can make developers more or less productive,
• they can encourage or instead discourage entire classes of errors,
• they can help or hinder reuse of code,
• they can make developers more or less happy.

With brute force and billions of dollars, you can overcome many programming languages deficiencies. But it remains a waste of valuable resources to write code in an inferior language. Apple has now shown that it understands that and has acted on it, and they should be commended for it.

Second, concepts which many Objective-C developers might not have been familiar with, like closures, immutable variables, functional programming, generics, pattern matching, and probably more, will now be absorbed and understood. This will lead to better, more maintainable programs. This will also make these developers interested in other languages, like Scala, which push some of these concepts further. The bar will be generally raised.

Finally, arguments over the heavy, ugly syntax of Objective-C, and its lack of modern features can be put to rest: Apple has decided the future path for iOS and OS X developers. That ship has sailed.

Where it fits

What kind of language is Swift? I noticed on Twitter that many had a bit of trouble positioning the language. Did Apple reinvent JavaScript? Or Go? Is Swift functional first? Is it even like Scala? What about C#? Or Clojure or XQuery?

I haven’t seen anything in Swift that is not in other programming languages. In fact, Swift features can be found in dozens of other languages (in Lattner’s own words, “drawing ideas from Objective-C, Rust, Haskell, Ruby, Python, C#, CLU, and far too many others to list”), and that’s why many have found similarities with their language of choice. So Swift is not “innovative”. Instead it is a reasonable mix and match of features which make sense for the Apple ecosystem.

Here are a few essential aspects of Swift which are not language features but which put it in context. These all appear to be essential to Apple:

1. Owned by Apple: Swift is fully owned by Apple. It does not depend on Oracle (Java/JVM), Microsoft (.NET), or Google.

2. Objective-C integration: Swift is designed to integrate really well with Objective-C. In fact, this is likely the second most important reason Apple felt they had to create their own language (in addition to ownership). There are precedents: Groovy, Scala, Clojure, Kotlin, Ceylon and others are designed to interoperate well with Java; CoffeeScript with JavaScript; Hack with PHP; Microsoft’s CLR was designed from the get go as a multi-language VM. This is important for initial adoption so that existing code can be reused and the new language progressively introduced. It would have been possible, but much harder, for Apple to pick an existing language.

3. Static typing: Swift is a statically-typed language. There is type inference, which means you don’t have to actually write down the types everywhere, in particular within functions. But types are there nonetheless. So it looks more like dynamic languages, but is not one. [3]

4. A dynamic feel: This is part of the “modern” aspect of Swift: a move toward concision which appeals to programmers used to dynamic languages, but with the presence of static typing under the hood. This combination of terseness and static typing is something Swift shares with Scala.

   Swift has a REPL and Playgrounds (the interactive demo by Chris Lattner looked impressive), which includes what some other environments call “worksheets” and a bit more. Clearly that’s the direction development tools are taking. All of this is becoming mainstream, which again raises the bar.

5. Native compilation: Swift is compiled down to native code, like C, C++, Objective-C, Go, and Rust. There is no interpreter or VM, as in Java, JavaScript, C#, Ruby, PHP, or all dynamic languages, besides the small Objective-C runtime. Also, it doesn’t have a real garbage collector: it uses automatic reference counting (ARC).

   Swift is a bit odd in that native compilation and lack of full garbage collection make it closer to systems language, yet it is clearly designed to build applications. I wish the balance had moved more toward the higher level rather than the lower level, but it’s an interesting middle ground.

What’s disappointing

Here are a few aspects of Swift which, at first glance, disappoint me a bit. Keeping in mind that this is a first version of Swift which has room to grow:

1. Openness: So far Apple has not announced that the Swift compiler would be open source, like the Objective-C compiler. This is a big question mark. It would be the right thing for them to do to open the compiler, and I am hopeful that they will.

2. Garbage collection: It’s likely that Apple considered that ARC was good enough in most situations, and it makes interoperability with Objective-C (compatibility in terms of memory management) much easier to handle. Still, this would give me trouble. Lack of proper garbage collection means more memory bugs to hunt down.

3. Concurrency support: Swift doesn’t have async/await, like C#, Scala, and soon JavaScript, or futures and promises. Async support is important in client apps as much as in server apps.

4. Type system: The type system appears very simple. This might be seen as good or bad. The reference book doesn’t even mention the word “variance”. (I suppose Swift picks a default, but doesn’t allow programmers to control that.)

5. Persistent data structures: There doesn’t seem to be persistent data structures (which are truly immutable yet can be updated efficiently thanks to structural sharing), as in Clojure and Scala. These are incredible tools which many programmers have now found to be essential. Immutability, in general, gives you much increased confidence about the correctness of your code. I would miss them in Swift.

6. Well, innovation: Dart, Go, Hack, and Swift show that it is very hard for big companies to come up with something really unique in their programming languages. Academia remains the place where new ideas are born and grow. Still, it would have been nice if there was one or two new things in Swift that would make it special, like for example Scala’s implicits which have turned out to have far-reaching consequences (several of which I really like).

Browser and server

I am curious to see if Swift will see adoption on the server, for services. It might make sense for Apple to use Swift internally for their services, although having a language is not enough: you need proper infrastructure for concurrent and distributed computing. Swift is not there yet. But it could be in the future. This is a bit less important to Apple than the client at this time.

What about the browser? Could one conceivably create a Swift-to-JavaScript compiler? I don’t see why not. JVM languages, from Java to Clojure to Scala, now compile to JavaScript. Swift currently uses ARC, but in a browser environment it could probably work with the JavaScript VM’s garbage collector.

So there might be room, in years to come, for Swift to conquer more environments.

Google!

Where does Google stand with regards to this? It’s curious, but I think now that it’s Google which might have a programming language problem! Android uses Java but, as famous programming languages guy Erik Meijer tweeted, “Swift makes Java look tired.” (To be fair, most languages make Java look tired.)

Google also has Dart, which so far hasn’t been positioned as a language to develop Android or server apps. But maybe that will come. Go is liked by some for certain types of server applications, but is even more of a “systems language” than Swift, and again Google hasn’t committed to bringing it as a language to write Android apps.

Will Google come up with yet another programming language, targeted at Android? The future will tell. If it was me, which of course it isn’t, Scala or a successor would be my choice as a great, forward-looking language for Android. And Google could point their Android developers to Scala and say “Look, it looks very much like Swift which you already know!” ;)

Did I miss anything? Let me know in the comments or on Twitter.

Scala collections and equality

Scala collections follow a simple set of general equality rules[1]. Two collections are equal if:

• they are in the same overall category (Seq, Set, or Map)
• they contain the same elements (as defined by ==)
• for sequences, the elements are in the same order

This means the following:

scala> List(1, 2, 3) == Vector(1, 2, 3)
res0: Boolean = true

scala> List(1, 2, 3) == Set(1, 2, 3)
res1: Boolean = false

scala> Set(1, 2, 3) == collection.mutable.LinkedHashSet(3, 1, 2)
res2: Boolean = true

Arrays don’t behave

The gotcha is that these rules break down with arrays:

scala> List(1, 2, 3) == Array(1, 2, 3)
res3: Boolean = false

And even:

scala> Array(1, 2, 3) == Array(1, 2, 3)
res4: Boolean = false

Why is this? The answer is that arrays in Java are treated specially all the way down to the JVM, and Scala arrays are just plain Java arrays. It is not possible to extend a JVM array, and this means in particular that it is not possible to override equals on arrays. Since native array eqality via equals does not compare array content, arrays are left to behave differently from Scala collections.

Solutions

So how do you go about comparing arrays in a way compatible with other Scala collections? First, there is an implicit conversion from Array to collection.mutable.WrappedArray, which is a Seq, so you can write:

scala> (Array(1, 2, 3): WrappedArray[Int]) == (Array(1, 2, 3): WrappedArray[Int])
res5: Boolean = true

Or even shorter:

scala> (Array(1, 2, 3): Seq[Int]) == (Array(1, 2, 3): Seq[Int])
res6: Boolean = true

Of course this also works if you pass an array to anything which expects a Seq:

scala> def sameStuff(s1: Seq[Int], s2: Seq[Int]) = s1 == s2
foo: (s1: Seq[Int], s2: Seq[Int])Boolean

scala> sameStuff(Array(1, 2, 3), Array(1, 2, 3))
res7: Boolean = true

From a memory perspective, this is not too bad because WrappedArray doesn’t make an expensive copy of the collection and instead just wraps the array.[2] But there is boxing going on with WrappedArray because it’s not a value class [3] (or rather concrete implementations of it are not value classes). Value classes cannot override equality[4], and a WrappedArray couldn’t be a proper Seq if that were the case.[5]

There is another way to compare array content with sameElements:

scala> Array(1, 2, 3) sameElements Array(1, 2, 3)
res8: Boolean = true

The benefit is that this more explicitly states the intent, and you don’t need to convert the arrays to Seq via type declarations.

Nested arrays

Both solutions above only work if arrays are not nested. Consider:

scala> Array(Array(11), Array(21, 22)) sameElements Array(Array(11), Array(21, 22))
res9: Boolean = false

The reason is that sameElements (or == on WrappedArray) just calls == on each array element. If those elements are arrays, Java array equality kicks in again (and we know that array content is not compared in that case).

Instead you can use the deep method:

scala> Array(Array(11), Array(21, 22)).deep == Array(Array(11), Array(21, 22)).deep
res10: Boolean = true

The deep method wraps arrays so that each access to an array element is first checked: if the element itself is an array, it is wrapped with WrappedArray first.[6] This way equality recursively works (but only if each array is directly nested in an array!).

It is generally safe to use deep instead of sameElements or a conversion to WrappedArray, but the implementation of deep requires a number of pattern matches, which are not known to be the fastest. If the arrays are known to be flat, the other approaches might be more efficient.

Case classes

Consider this case class:

scala> case class Foo(a: Array[Int])
defined class Foo

scala> Foo(Array(1)) == Foo(Array(1))
res11: Boolean = false

By now you know why this happens: the case class provides an implementation of == for you, but doesn’t treat arrays specially. If equality matters to you (and it probably should if you use case classes), it is better to write instead something like this:

scala> case class Foo(a: Seq[Int])
defined class Foo

scala> Foo(Array(1)) == Foo(Array(1))
res12: Boolean = true

Here the case class actually refers to a WrappedArray, obtained via implicit conversion from the original array.

Words of wisdom

The equality issue suggests that it is wise to avoid arrays when possible. If you cannot avoid them, beware of the semantic of equality on them! But since arrays offer interoperability with Java and are compact, native data structures that offers performance benefits, it’s often hard to live without them entirely.

There are a number of StackOverflow questions that cover this topic as well.[7] Please let me know if I omitted anything important!

I just hit a bug caused by a misunderstanding of how Map.mapValues works. Consider:

val original = Map("a" → 1, "b" → 2)
val modified = original map { case (k, v) ⇒ k → (v + 1) }

The result is an immutable map[1] which is a transformation of the original map (all values are incremented by one). Once the map method terminates, the new map is actually holding those new values.

Now Map also has a mapValues method, which seems like an attractive shortcut for the rather verbose transformation above. So you write:

val original = Map("a" → 1, "b" → 2)
val modified = original mapValues (_ + 1)

More concise, right? But there is a catch: map and mapValues are different in a not-so-subtle way. mapValues, unlike map, returns a view on the original map. This view holds references to both the original map and to the transformation function (here (_ + 1)). Every time the returned map (view) is queried, the original map is first queried and the tranformation function is called on the result. You can see this in the source code of the Scala standard library:

override def mapValues[C](f: B => C): Map[A, C] = new DefaultMap[A, C] {
  ...
  def get(key: A) = self.get(key).map(f)
}

If the transformation function is referentially transparent, like (_ + 1), all is well (besides performance considerations). But if not, you might be in for fun bugs depending on when the resulting map is queried. In my case, the transformation function depended on a context which, at a later point, was made invalid. When the resulting map was queried, the function-that-really-shouldn’t-run-now was running in that invalidated context and causing trouble.

There is nothing inherently wrong with providing a view on the original map, but I would say the naming of mapValues violates the principle of least surprise: everybody knows the map method, and might reasonably assume that mapValues would behave in a similar way (and it doesn’t).

Morality: when using mapValues, make sure the implications of using a view are acceptable, including making sure that your transformation function can safely run at the time the resulting map is queried. If not, prefer the good old map method. Oh, and also try to keep mutations local (but it’s often not easy).

In Scala, you have a few ways to express that a function returns the Unit type.[1] A common way is to use the function syntax and specify a result type of Unit:

def foo: Unit = ...

Like for any result type, the type annotation is not necessary if the function body already returns the expected type, as in:

def newline = println()

or:[2]

trait Foo {
  def log = ()
}

The type annotation is useful not only for documentation purposes, but also in case the last expression of the function body happens to return a result of a type which is not Unit:

def focus(): Boolean = ...    // function with side effect but which also returns a value
def justFocus: Unit = focus() // function with side effect returning Unit

Now you might wonder, as @avernet and I did yesterday, how this last bit can work! How does the compiler, with an expected type of Unit on one hand, and an actual expression type of Boolean on the other hand, reconcile the two?

This is not done via subtyping, because Unit is not a supertype of Boolean: instead Unit is a subtype of AnyVal and at the same level as Boolean in the Scala type hierarchy.

The answer is that there is an implicit conversion taking place.[3] The Scala language specification specifies this conversion in section 6.26.1:

Value Discarding. If e has some value type and the expected type is Unit, e is converted to the expected type by embedding it in the term { e; () }.

In case you are wondering, here value type does not mean a subtype of AnyVal. This can be a bit misleading, especially with the introduction in Scala 2.10 of value classes, which do derive from AnyVal. Instead, a value type is just a type which can have concrete values, as explained in chapter 3 of the spec:

A subset of first-order types called value types represents sets of (first-class) values. […] Non-value types capture properties of identifiers that are not values (§3.3). For example, a type constructor (§3.3.3) does not directly specify a type of values."

In short the spec mandates that any value returned by an expression is implicitly converted to Unit by the compiler when the expected type is Unit. This applies in particular to functions, where the expression is the function body and the expected type is determined with the Unit type annotation.

So now we all know how it works!

Recently I needed to write a pretty simple function: given a sequence of (name, value) pairs, return a sequence of (name, some collection of all the values having that name) pairs. Here is a simple implementation:

def combineValues(pairs: Seq[(String, String)]): Seq[(String, Seq[String])] = {
  val result = LinkedHashMap[String, List[String]]()

  for ((name, value) ← pairs)
    result += name → (value :: result.getOrElse(name, Nil))

  result.toList
}

Then I realized that I not only needed the result as a Seq[(String, Seq[String])], but also as a Seq[(String, Array[AnyRef])], for compatibility with a Java API. I could of course transform one into the other, but I wondered whether there might be a way to directly return the desired collection type (without duplicating the function!).

Let’s think a little bit about what this entails: the revised combineValues needs to create new collections of a type specified by the caller. So first the type needs to be specified, which means that the function needs to take so-called type parameters: one for the resulting collection type, and one for the item type:

import language.higherKinds // so that Scala 2.10 doesn't warn
def combineValues[U, T[_]](pairs: Seq[(String, String)]): Seq[(String, T[U])]

The type parameters are specified with the funny [U, T[_]] declaration before the usual function parameters. You have probably seen this syntax on generic classes. But functions can have type parameters too!

Also, the function now says it returns values of type T[U]. The idea here is that we will return collections of type T where T stands for things like Seq, Array and Set containing elements of type U, where U stands for String or AnyRef.

Do you see what we’ve done here? We have changed the signature to be more abstract: instead of specifying beforehand that we are dealing with Seq or Array or String, we use “variables” (T and U). In case you are wondering, there is nothing magic about the names T and U, we could have used Coll and Elem instead. It’s a matter of taste.

A couple of remarks on the syntax:

• It’s not possible to just specify [T[U]] as a single type parameter: the two parameters must be separate.
• Because T is a type which itself takes a parameter, we must say so with T[_] (T[Whatever] works too).

Here is how you call the function with explicit type parameters (sometimes, type parameters can be inferred by the compiler, but not here):

combineValues[String, List](seq)

Now the function needs to make use of these type parameters to create the new collections. How do we do that?

Naively, let’s try creating new empty collections of type T[U] using a constructor:

new T[U] // incorrect Scala

or, using a companion object’s apply:

T[U]() // incorrect Scala

Unfortunately, neither even compiles. How would something like this work anyway? You could imagine that the runtime type information is available to combineValues and then use reflection to create new instances. But:

• Scala erases parametrized types during compilation, and type parameters are not automatically available at runtime (although there are ways to obtain them).
• The collection type parameter could be a trait, like Seq, in which case you would have to find a reasonable concrete class implementing that trait. How would you go about making that determination?
• This would result in instantiating empty instances of the resulting collection. How would you add elements to that collection? Array and List in particular aren’t Growable collections. So you would have to find a constructor taking all the items of the collection instead. That’s possible, but not guaranteed to work at runtime for all types.
• This might not be very efficient due to the use of reflection.

So besides the fact that it does not work out of the box, this approach is not as simple as it first looked. We are missing something, and that something is a factory for the collection to create. And Scala already has a trait for that kind of factories in the Scala standard library: it is called CanBuildFrom.

This trait is a bit of a funny thing: it is part of many Scala collections function signatures, and for that reason has been the target of criticism, with the result that Scala 2.8’s Scaladoc hides it from signatures by default. Some have argued that it’s not necessary to understand it to use Scala collections, and I agree with that (in general, Scala collections just work even if you don’t have any idea that CanBuildFrom exists).

This said, CanBuildFrom itself is a pretty simple thing conceptually: if you have an instance of CanBuildFrom for a given collection type, you can call apply on it to get a Builder for that collection. Once you have the builder, you just add elements to it, and finally obtain the resulting collection. The trait itself is parametrized, to specify a source collection type, an element type, and a resulting collection type: CanBuildFrom[-From, -Elem, +To].

Here, what we want is a CanBuildFrom[T[U], U, T[U]]. The first type parameter, the From collection, does not seem to be consequential here.) In short it’s a factory able to return a Builder for a collection T[U].

A version of our function receiving a CanBuildFrom looks like this:

def combineValues[U, T[_]](
  pairs : Seq[(String, String)],
  cbf   : CanBuildFrom[T[U], U, T[U]]
): Seq[(String, T[U])] = {

  val result = LinkedHashMap[String, Builder[String, T[U]]]()

  for ((name, value) ← pairs)
    result.getOrElseUpdate(name, cbf()) += value

  result map { case (k, v) ⇒ k → v.result } toList
}

Note where the factory is called: cbf(), and where the resulting collection is obtained: v.result.

But how does the caller even obtain a CanBuildFrom? You have not only to pass T and U (the type parameters) but also somehow figure out where to locate that factory.

Of course, and this is why the Scala collections and CanBuildFrom are designed this way in the first place, there is a twist: implicit parameters. The idea is that instead of finding and passing the factory explicitly to the function, the compiler does that for you. So we change the signature as follows:

def combineValues[U, T[_]](pairs: Seq[(String, String)])
  (implicit cbf: CanBuildFrom[T[U], U, T[U]]): Seq[(String, T[U])]

Notice how we changed cbf from a regular parameter to an implicit parameter with the implicit keyword, and moved it to a second parameter list (yes, Scala supports more than one parameter list).

When the compiler sees a call to such a function, it does something called an implicit search. This is the process whereby it locates an appropriate value for the implicit parameter, based on the function scope and parameters (see more on implicit search). Importantly, it looks at the type of the implicit parameter. Here this means that the value must be of type CanBuildFrom, with the proper type parameters too.

The Scala collections have such factories already, and they are nicely made available to implicit search when you use collection types such as Seq and Array. So the compiler will find them without trouble.

So say we call the function like this:

combineValues[AnyRef, Array](seq)
combineValues[String, List](seq)

The compiler will respectively search for the following CanBuildFrom instances, and pass them to the function:

CanBuildFrom[Array[AnyRef], AnyRef, Array[AnyRef]]
CanBuildFrom[List[String], String, List[String]]

And it will just work!

The result? We have a achieved more than what we were looking for: we have a function able to return a result made of any existing collection available in the standard library, or even outside of the standard library, for that matter. The resulting collection can be anything you want as long as there is a CanBuildFrom for the resulting type. Most notably, Array is a plain Java array, and it works because Scala provides a CanBuildFrom for it. It’s a powerful approach.

From the caller side, things remain easy: you call your function as usual except that you specify the type of the result you want.

Is there magic here? No: it is all done thanks to the clever design of implicit parameters and their use within the standard Scala collections. And the great thing is that the mechanics of it are available to anybody, not just to the compiler or Scala standard library maintainers.

What to think of the type parameters and the implicit CanBuildFrom factory? They certainly lead to more abstract programming, but when put in simple terms, like “here is a function which can return a result based on any collection type you want, as long as the compiler finds a factory for that type”, I think it sounds quite reasonable.

Following-up on the previous post about iterators, say we have a clean Scala API with Option instead:

class Foo { def parent: Option[Foo] =  … }
def findBar(foo: Foo) = Option[Bar] = …

It turns out that Iterator.iterate falls apart with Option, because it requires a function returning a plain T. But we can write a better Option-aware iterate function:

def iterate[T](start: T)(f: T ⇒ Option[T]): Iterator[T] = new Iterator[T] {
  private[this] var acc = Option(start)
  def hasNext = acc.isDefined
  def next() = {
    val result = acc.get
    acc = f(result)
    result
  }
}

Note that this iterate does not depend at all on application-specific code. In fact, it could be part of the standard Scala library!

With this new tool, the new ancestorOrSelf iterator simply looks like this:

def ancestorOrSelf(foo: Foo) =
  iterate(foo)(_.parent)

And one way to write findInAncestorOrSelf becomes:

def findInAncestorOrSelf(foo: Foo) =
  ancestorOrSelf(foo) map findBar find (_.isDefined) flatten

Now to be honest this last function is not fully satisfying, with its use of isDefined and its hanging flatten in the end! There are other ways to write it, including with collectFirst, but still it’s not quite right.

The root issue is that Scala.Iterator doesn’t have a headOption (or a nextOption) method. Until that’s the case we can write our own extension method like this:

class MyIteratorOps[T](i: Iterator[T]) { def nextOption = if (i.hasNext) Option(i.next) else None }
implicit def toIteratorOps[T](i: Iterator[T]) = new MyIteratorOps(i)

or, with Scala 2.10:

implicit class MyIteratorOps(i: Iterator[T]) {
  def nextOption = if (i.hasNext) Option(i.next) else None
}

Again, this is something which could be in the standard Scala library. With this the final code becomes the much cleaner:

def findInAncestorOrSelf(foo: Foo) =
  ancestorOrSelf(foo) flatMap findBar nextOption

In the end it’s probably a matter of taste, but I would almost bet that as a programmer familiar with Scala collections, you would find this function immediately comprehensible. That’s a huge win in addition to the increased modularity gained through the use of iterators.

There is a common programming pattern where you navigate a hierarchy in order to find an element satisfying a certain condition. I have written code like this in Java probably a million times:

class Foo { public Foo getParent() { … } }
public Bar findBar(Foo foo) { … }

Bar findInAncestorOrSelf(Foo foo) {
    Foo currentFoo = foo;
    while (currentFoo != null) {
        Bar possibleResult = findBar(currentFoo);
        if (possibleResult != null)
            return possibleResult;
        currentFoo = currentFoo.getParent();
    }
    return null;
}

It is probably efficient but it’s not easy to read, it screams “boilerplate”, and it mixes two concerns:

• navigating the hierarchy
• doing something with elements in the hierarchy

So while you can write in the same style in Scala, there is a better way which starts with iterators. You probably know about the Java Iterator interface, which allows you to iterate over collections and also underlies the “for-each” construct. Scala also has an Iterator trait, which looks a lot like Java’s construct but supports lots of useful functions. In fact it supports most of the functions found in Traversable (which is the base trait of every Scala collection).

This makes Scala iterators immensely more useful than Java’s: implementing an iterator takes a few lines of code and instantly you have access to dozens of functions including foreach, find, map, filter, ++.

So what if you use an iterator to implement findInAncestorOrSelf above? You can implement your own iterator, but it just happens that here the built-in Iterator.iterate helps us bit: this function takes a starting object and a function to obtain the next object, and returns an iterator. Here is one which navigates all ancestors forever:

def ancestorOrSelf(foo: Foo) =
  Iterator.iterate(foo)(_.getParent)

And here is one which actually stops when there are no more ancestors:

def ancestorOrSelf(foo: Foo) =
  Iterator.iterate(foo)(_.getParent) takeWhile (_ ne null)

You can use that iterator to achieve the same as the original Java code (except it returns an Option[Bar]):

def findInAncestorOrSelf(foo: Foo) =
  ancestorOrSelf(foo) map findBar find (_ ne null)

It’s short and to the point, and the great thing is that you can use the iterator to do any kind of search or transformation of elements in the hierarchy: navigation is completely independent from the rest.

See also More iterators goodness.