How to write a zipWith method that returns the same type of collection as those passed to it?

Question

I have reached this far:

implicit def collectionExtras[A](xs: Iterable[A]) = new {
  def zipWith[B, C, That](ys: Iterable[B])(f: (A, B) => C)(implicit cbf: CanBuildFrom[Iterable[A], C, That]) = {
    val builder = cbf(xs.repr)
    val (i, j) = (xs.iterator, ys.iterator)
    while(i.hasNext && j.hasNext) {
      builder += f(i.next, j.next)
    }
    builder.result
  }
}
// collectionExtras: [A](xs: Iterable[A])java.lang.Object{def zipWith[B,C,That](ys: Iterable[B])(f: (A, B) => C)(implicit cbf: scala.collection.generic.CanBuildFrom[Iterable[A],C,That]): That}

Vector(2, 2, 2).zipWith(Vector(4, 4, 4))(_ * _)
// res3: Iterable[Int] = Vector(8, 8, 8)

Now the problem is that above method always returns an Iterable. How do I make it return the collection of type as those passed to it? (in this case, Vector) Thanks.

Answer 1

You got close enough. Just a minor change in two lines:

implicit def collectionExtras[A, CC[A] <: IterableLike[A, CC[A]]](xs: CC[A]) = new {
  def zipWith[B, C, That](ys: Iterable[B])(f: (A, B) => C)(implicit cbf: CanBuildFrom[CC[A], C, That]) = {
    val builder = cbf(xs.repr)
    val (i, j) = (xs.iterator, ys.iterator)
    while(i.hasNext && j.hasNext) {
      builder += f(i.next, j.next)
    }
    builder.result
  }
}

First, you need to get the collection type being passed, so I added CC[A] as a type parameter. Also, that collection needs to be able to "reproduce" itself -- that is guaranteed by the second type parameter of IterableLike -- so CC[A] <: IterableLike[A, CC[A]]. Note that this second parameter of IterableLike is Repr, precisely the type of xs.repr.

Naturally, CanBuildFrom needs to receive CC[A] instead of Iterable[A]. And that's all there is to it.

And the result:

scala> Vector(2, 2, 2).zipWith(Vector(4, 4, 4))(_ * _)
res0: scala.collection.immutable.Vector[Int] = Vector(8, 8, 8)

Answer 2

The problem above is that your implicit conversion collectionExtras causes the obtained object to lose type information. In particular, in the solution above, the concrete collection type is lost because you're passing it an object of type Iterable[A] - from this point on, the compiler no longer knows the real type of xs. Although the builder factory CanBuildFrom programatically ensures that the dynamic type of the collection is correct (you really get a Vector), statically, the compiler knows only that zipWith returns something that is an Iterable.

To solve this problem, instead of having the implicit conversion take an Iterable[A], let it take an IterableLike[A, Repr]. Why?

Iterable[A] is usually declared as something like:

Iterable[A] extends IterableLike[A, Iterable[A]]

The difference with Iterable is that this IterableLike[A, Repr] keeps the concrete collection type as Repr. Most concrete collections, in addition to mixing in Iterable[A], also mix in the trait IterableLike[A, Repr], replacing the Repr with their concrete type, like below:

Vector[A] extends Iterable[A] with IterableLike[A, Vector[A]]

They can do this because type parameter Repr is declared as covariant.

Long story short, using IterableLike causes you implicit conversion to keep the concrete collection type information (that is Repr) around and use it when you define zipWith - note that the builder factory CanBuildFrom will now contain Repr instead of Iterable[A] for the first type parameter, causing the appropriate implicit object to be resolved:

import collection._
import collection.generic._

implicit def collectionExtras[A, Repr](xs: IterableLike[A, Repr]) = new {
  def zipWith[B, C, That](ys: Iterable[B])(f: (A, B) => C)(implicit cbf: CanBuildFrom[Repr, C, That]) = {
    val builder = cbf(xs.repr)
    val (i, j) = (xs.iterator, ys.iterator)
    while(i.hasNext && j.hasNext) {
      builder += f(i.next, j.next)
    }
    builder.result
  }
}

Reading your question formulation more carefully ("How to write a zipWith method that returns the same type of collection as those passed to it?"), it seems to me that you want to have the same type of collection as those passed to zipWith, not to the implicit conversion, that is the same type asys.

Same reasons as before, see solution below:

import collection._
import collection.generic._

implicit def collectionExtras[A](xs: Iterable[A]) = new {
  def zipWith[B, C, That, Repr](ys: IterableLike[B, Repr])(f: (A, B) => C)(implicit cbf: CanBuildFrom[Repr, C, That]) = {
    val builder = cbf(ys.repr)
    val (i, j) = (xs.iterator, ys.iterator)
    while(i.hasNext && j.hasNext) {
      builder += f(i.next, j.next)
    }
    builder.result
  }
}

With results:

scala> immutable.Vector(2, 2, 2).zipWith(mutable.ArrayBuffer(4, 4, 4))(_ * _)
res1: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(8, 8, 8)

Answer 3

or you can cast it:

builder.result.asInstanceOf[Vector[A]]

Answer 4

To be honest I'm not sure how that really works:

implicit def collectionExtras[CC[X] <: Iterable[X], A](xs: CC[A]) = new {
  import collection.generic.CanBuildFrom
  def zipWith[B, C](ys: Iterable[B])(f: (A, B) => C)
  (implicit cbf:CanBuildFrom[Nothing, C, CC[C]]): CC[C] = {
    xs.zip(ys).map(f.tupled)(collection.breakOut)
  }
}

scala> Vector(2, 2, 2).zipWith(Vector(4, 4, 4))(_ * _)
res1: scala.collection.immutable.Vector[Int] = Vector(8, 8, 8)

I sort of monkey patched this answer from retronym until it worked!

Basically, I want to use the CC[X] type constructor to indicate that zipWith should return the collection type of xs but with C as the type parameter (CC[C]). And I want to use breakOut to get the right result type. I sort of hoped that there was a CanBuildFrom implicit in scope but then got this error message:

required: scala.collection.generic.CanBuildFrom[Iterable[(A, B)],C,CC[C]]

The trick was then to use Nothing instead of Iterable[(A, B)]. I guess that implicit is defined somewhere...

Also, I like to think of your zipWith as zip and then map, so I changed the implementation. Here is with your implementation:

implicit def collectionExtras[CC[X] <: Iterable[X], A](xs: CC[A]) = new {
  import collection.generic.CanBuildFrom
  def zipWith[B, C](ys: Iterable[B])(f: (A, B) => C)
  (implicit cbf:CanBuildFrom[Nothing, C, CC[C]]) : CC[C] = {
    val builder = cbf()
    val (i, j) = (xs.iterator, ys.iterator)
    while(i.hasNext && j.hasNext) {
      builder += f(i.next, j.next)
    }
    builder.result
  }
}

Note this article provides some background on the type constructor pattern.