How to enrich a TraversableOnce with my own generic map?

Question

I am trying to enrich all TraversableOnce[String] objects, and I can't figure out the right syntax for building iterators. This is what I have so far:

class Exclaimer[R <: TraversableOnce[String]](val lines:R) {
  import scala.collection.generic.CanBuildFrom
  def exclaim(implicit bf:CanBuildFrom[R,String,R]):R = {
    val b = bf(lines)
    lines.foreach(b += _)
    b.result
  }
}
implicit def WrapExclaimer[R <: TraversableOnce[String]](lines:R) = new Exclaimer(lines)

It works fine for collections (i.e. it returns an collection of the same class as I gave it), but it doesn't work for iterators, because it Cannot construct a collection of type Iterator[java.lang.String] with elements of type String based on a collection of type Iterator[java.lang.String]. How do I fix this? I'm using Scala 2.9 (edit: I mistakenly wrote 2.8).

Here is some sample output:

scala> List("a","b","c").exclaim
res5: List[java.lang.String] = List(a, b, c)

scala> Vector("a","b","c").exclaim
res6: scala.collection.immutable.Vector[java.lang.String] = Vector(a, b, c)

scala> List("a","b","c").iterator.exclaim
<console>:10: error: Cannot construct a collection of type Iterator[java.lang.String] with elements of type String based on a collection of type Iterator[java.lang.String].
              List("a","b","c").iterator.exclaim
                                         ^

Answer 1

General solution for 2.10

You should use exclaim[That](implicit bf:CanBuildFrom[R, String, That]) instead of CanBuildFrom[R,String,R]. Note also that there is more general way to extend collection-like classes - IsTraversableOnce (and also IsTraversableLike)

import collection.generic.IsTraversableOnce
import collection.GenTraversableOnce

class Exclaimer[A, Repr](val lines: GenTraversableOnce[A]) {
  import scala.collection.generic.CanBuildFrom
  def exclaim[That](implicit bf:CanBuildFrom[Repr, String, That], e: A =:= String): That = {
    val b = bf()
    lines.foreach(s => b += e(s))
    b.result
  }
}
implicit def wrapExclaimer[Repr](r: Repr)(implicit fr: IsTraversableOnce[Repr]): Exclaimer[fr.A,Repr] =
  new Exclaimer[fr.A, Repr](fr.conversion(r))

This method works with Array:

Array("a","b","c").exclaim
// Array[String] = Array(a, b, c)

Fixed initial implementation

Here is your initial implementation (fixed). It works with Iterator, but fails on Array since Array is not TraversableOnce:

class Exclaimer[R <: TraversableOnce[String]](val lines:R) {
  import scala.collection.generic.CanBuildFrom
  def exclaim[That](implicit bf:CanBuildFrom[R,String,That]):That = {
    val b = bf(lines)
    lines.foreach(b += _)
    b.result
  }
}
implicit def WrapExclaimer[R <: TraversableOnce[String]](lines:R) = new Exclaimer(lines)

scala> List("a","b","c").iterator.exclaim
res0: Iterator[String] = non-empty iterator

scala> Array("a","b","c").exclaim
<console>:10: error: value exclaim is not a member of Array[String]
              Array("a","b","c").exclaim
                                 ^

CanBuildFrom

There is no IsTraversableOnce in scala 2.9.3, so you have to use fixed version of your initial approach. But you'll get TraversableOnce instead of Iterator.

List("a","b","c").iterator.exclaim
// scala.collection.TraversableOnce[String] = non-empty iterator

To get Iterator you have to create your own implicit CanBuildFrom like this:

import collection.generic.CanBuildFrom
import collection.mutable.Builder
import collection.immutable.VectorBuilder

implicit def iteratorCbf[A, B] = new CanBuildFrom[Iterator[A], B, Iterator[B]]{
  def apply(): Builder[B, Iterator[B]] = new Builder[B, Iterator[B]]{
    private[this] val inner = new VectorBuilder[B]
    def +=(elem: B) = {
      inner += elem
      this
    }
    def clear(): Unit = inner.clear()
    def result(): Iterator[B] = inner.result().iterator
  }
  def apply(i: Iterator[A]) = apply()
}

No you'll get Iterator[String] instead of TraversableOnce[String]:

List("a","b","c").iterator.exclaim
// Iterator[String] = non-empty iterator

You should add implicit iteratorCbf method into companion object of your Exclaimer class.

Answer 2

The cleanest answer, I think, is Don't try to enrich TraversableOnce with a generic map. The point of TraversableOnce is that it covers both Iterators and Collections -- but the only way to generically enrich a TraversableOnce (with Scala 2.10) is to turn the iterator into a collection and back into an iterator, which defeats the point of the iterator (or at least one point: being able to stream huge datasets without loading them all into memory).

I had naively thought that because Iterator.map and Collection.map have the same syntax, they had a common implementation, and so I was trying to find a common implementation for my Exclaimer map. However, looking at the Scala source code, we see that Iterator.map and Collection.map have different implementations:

// Implementation of map in TraversableOnce[+A] implicit typecast to MonadOps[+A]
def map[B](f: A => B): TraversableOnce[B] = trav.toIterator map f

// Implementation of map in Iterator[+A]
def map[B](f: A => B): Iterator[B] = new AbstractIterator[B] {
  def hasNext = self.hasNext
  def next() = f(self.next())
}

// Implementation of map in TraversableLike[+A, +Repr]
def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
  def builder = { // extracted to keep method size under 35 bytes, so that it can be JIT-inlined
    val b = bf(repr)
    b.sizeHint(this)
    b
  }
  val b = builder
  for (x <- this) b += f(x)
  b.result
}

Moral: If the Scala designers decided not to write a generic map function for TraversableOnce, then I shouldn't try to either.

Here is the code I ended up with, thanks to @senia.

class TraversableExclaimer[R <: Traversable[String]](val lines:R) {
  import scala.collection.generic.CanBuildFrom
  def exclaim[That](implicit bf:CanBuildFrom[R,String,That]):That = {
    val b = bf(lines)
    lines.foreach(b += _+"!")
    b.result
  }
}
implicit def WrapTraversableExclaimer[R <: Traversable[String]](lines:R) = new TraversableExclaimer[R](lines)

class IteratorExclaimer[T <: String](val lines:Iterator[T]) {
  def exclaim:Iterator[T] = new Object with Iterator[T] {
    def hasNext = lines.hasNext
    def next() = (lines.next()+"!").asInstanceOf[T]
  }
}
implicit def WrapIteratorExclaimer(lines:Iterator[String]) = new IteratorExclaimer[String](lines)