Why is Option not Traversable?

Question

Is there any rational for Option not being Traversable?

In Scala 2.9, Seq(Set(1,3,2),Seq(4),Option(5)).flatten doesn't compile and simply having it to implement the Traversable trait seams rational to me. If it's not the case, there must be something I don't see that don't allow it. What is it?

PS: While trying to understand, I achieved awful things that compile, like:

scala> Seq(Set(1,3,2),Seq(4),Map("one"->1, 2->"two")).flatten
res1: Seq[Any] = List(1, 3, 2, 4, (one,1), (2,two))

PS2: I know I can write: Seq(Set(1,3,2),Seq(4),Option(5).toSeq).flatten or other ugly thing.

PS3: There seams to be work in the last month to make Option look more like Traversable without implementing it: commit, another commit

Answer 1

There may be challenges around having flatMap return an Option rather than a Traversable. Though that predates the whole 2.8 CanBuildFrom machinery.

The question was asked once before on the mailing list but didn't elicit a response.

Here is an illustration:

sealed trait OptionX[+A] extends Traversable[A] {
  def foreach[U](f: (A) => U): Unit = if (!isEmpty) f(get)
  def get: A
  def isDefined: Boolean
  def getOrElse[B >: A](default: => B): B
}

case class SomeX[+A](a: A) extends OptionX[A] {
  override def isEmpty = false
  def get = a
  def isDefined = true
  def getOrElse[B >: A](default: => B) = a
}

case object NoneX extends OptionX[Nothing] {
  override def isEmpty = true
  def get = sys.error("none")
  def isDefined = false
  def getOrElse[B](default: => B) = default
}

object O extends App {
  val s: OptionX[Int] = SomeX(1)
  val n: OptionX[Int] = NoneX
  s.foreach(i => println("some " + i))
  n.foreach(i => println("should not print " + i))
  println(s.map(_ + "!"))
}

The last line returns a List("1!") instead of Option. May be somebody can come up with a CanBuildFrom that would yield an SomeX("1!"). My attempt did not succeed:

object OptionX {
  implicit def canBuildFrom[Elem] = new CanBuildFrom[Traversable[_], Elem, OptionX[Elem]] {
    def builder() = new Builder[Elem, OptionX[Elem]] {
      var current: OptionX[Elem] = NoneX
      def +=(elem: Elem): this.type = {
        if (current.isDefined) sys.error("already defined")
        else current = SomeX(elem)
        this
      }
      def clear() { current = NoneX }
      def result(): OptionX[Elem] = current
    }
    def apply() = builder()
    def apply(from: Traversable[_]) = builder()
  }
}

I need to pass the implicit explicitly:

scala> import o._
import o._

scala> val s: OptionX[Int] = SomeX(1)
s: o.OptionX[Int] = SomeX(1)

scala> s.map(_+1)(OptionX.canBuildFrom[Int])
res1: o.OptionX[Int] = SomeX(2)

scala> s.map(_+1)
res2: Traversable[Int] = List(2)

Edit:

So I was able to work around the issue and have SomeX(1).map(1+) return an OptionX by having OptionX extend TraversableLike[A, OptionX[A]] and overriding newBuilder.

But then I get runtime errors on SomeX(1) ++ SomeX(2) or for (i <- SomeX(1); j <- List(1,2)) yield (i+j). So I don't think it's possible have option extend Traversable and do something sane in terms of returning the most specific type.

Beyond feasibility, coding style wise, I'm not sure it's a good thing to have Option behave like a Traversable in all circumstances. Option represent values that are not always defined, while Traversable defines methods for collections that can have multiple elements in it like drop(n), splitAt(n), take(n), ++. Although it would offer convenience if Option was also a Traversable, I think it may make intent less clear.

Using a toSeq where necessary seems like a painless way to indicate that I want my option to behave like a Traversable. And for certain recurring use cases, there is the option2Iterable implicit conversion - so for instance this already works (they all return List(1,2)):

• List(Option(1), Option(2), None).flatten
• for (i <- List(0,1); j <- Some(1)) yield (i+j)
• Some(1) ++ Some(2)

Answer 2

It is not Traversable because you can't implement a scala.collection.mutable.Builder for it.

Well, it could be a Traversable even so, but that would result in a lot of methods that return Option now returning Traversable instead. If you want to see what methods are these, just look at the methods that take a CanBuildFrom parameter.

Let's take your sample code to demonstrate why:

Seq(Set(1,3,2),Seq(4),Option(5)).flatten

That ought to be equal to:

Seq(1, 2, 3, 4, 5)

Now, let's consider this alternative:

Option(Set(1,3,2),Seq(4),Option(5)).flatten

What's the value of that?

Answer 3

The reason is that in some cases with implicits applied the type would get less precise. You would still have an Option value, but the static return type would be something like Iterable, e. g. not the “most precise” one.

Answer 4

Perhaps I'm being dense, but I don't understand why anyone would need this. Furthermore, it would require None to be Traversable as well which seems semantically dubious.

They say a design is finished not when there is nothing left to add, but rather nothing left to take away. Which is not to say, of course, that the Scala standard library is perfect.