Why is Option not Traversable?

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)

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?