How can I add cross product based methods to scala collections?

Question

hopefully this will be a simple question about library pimping (because other questions on that subject tend to generate answers beyond my current skill level).

All I want to do is map over the cross product of a collection with itself.

val distances = points.crossMap(_ distance _)  // points: List[Point3d]

So I attempted to pimp Traversable thus:

implicit def toSelfCrossMappable[A](xs: Traversable[A]) = new {
  def crossMap[B](f: (A, A) => B) = xs.flatMap(a => xs.map(f(a, _)))
}

But it doesn't work (it's not doing the implicit conversion) and I don't understand why not (I'm pretty new to scala). I also tried the method suggested in Enriching Scala collections with a method which left me with:

implicit def toSelfCrossMappable[A, C[A]](xs: C[A])(implicit c: C[A] => Traversable[A]) = new SelfCrossable[A, C[A]](xs)(c)

class SelfCrossable[A, C](xs: C)(implicit c: C => Traversable[A]) {
  def crossMap[B](f: (A, A) => B) = xs.flatMap(a => xs.map(f(a, _)))
}

, but that throws the same error as my (simpler looking) way.

What am I doing wrong here?

`for(a <- points; b <- points) yield (a distance b)` or `points.flatMap{ a => points.map{ b => a distance b } }` — senia, May 06 '13 at 06:45
Ah, perhaps I should clarify, when I said "all I want to do is" what I really meant was "the core of the problem I'm having can be reduced to". There's more to the real problem that motivates me wanting to use implicit conversions. — teryret, May 06 '13 at 06:59
ok, might not be a solution to your problem as you say there is more to it. But there is a `combination` function in `SeqLike` traversables. — Mortimer, May 06 '13 at 17:27

score 10 · Accepted Answer · answered May 06 '13 at 10:06

10

It's not pretty, but this can be done with IsTraversableLike,

import scala.language.implicitConversions

import scala.collection.generic.{ CanBuildFrom, IsTraversableLike }
import scala.collection.GenTraversableLike

class SelfCrossMappable[A, Repr](xs: GenTraversableLike[A, Repr]) {
  def crossMap[B, That](f: (A, A) => B)
    (implicit
      cbf: CanBuildFrom[Repr, B, That],
      itl: IsTraversableLike[That] { type A = B }
    ) = xs.flatMap { a => itl.conversion(xs.map(f(a, _)))
  } 
}

implicit def toSelfCrossMappable[Repr](xs: Repr)
  (implicit traversable: IsTraversableLike[Repr]) =
    new SelfCrossMappable(traversable.conversion(xs))

Sample REPL session,

scala> List("foo", "foo", "bar").crossMap(_ == _)
res0: List[Boolean] = List(true, true, false, true, true, false, false, false, true)

answered May 06 '13 at 10:06

Miles Sabin

23,015
6
61
95

Is there a version that will work with 2.9? Also, if I were to ask why that works (and why mine didn't) would the answer fry my brain? – teryret May 06 '13 at 17:27
1

you might want to check the [The Architecture of Scala Collections](http://www.scala-lang.org/docu/files/collections-api/collections-impl_0.html) to understand what's going on with the `CanBuildFrom`. I don't think that you need so much knwoledge of advanced scala to get it. – Mortimer May 06 '13 at 17:28
I'd strongly recommend upgrading to 2.10, but if you can't, `IsTraversableLike` will compile under 2.9.x so you could copy its source from the Scala distribution into your project. – Miles Sabin May 06 '13 at 20:27

score 2 · Answer 2 · answered May 06 '13 at 17:51

In Scala 2.10 you can use implicit classes directly (Miles' answer uses the IsTraversableLike helper which also requires Scala 2.10). It seems that the toSelfCrossMappable (horrible name BTW) is not needed for standard collections. The following works for me:

import collection.generic.{CanBuildFrom, IsTraversableLike}
import collection.GenTraversableLike

implicit class CanCrossMap[A, Repr](xs: GenTraversableLike[A, Repr]) {
  def crossMap[B, That](f: (A, A) => B)(
    implicit cbf: CanBuildFrom[Repr, B, That], 
             itl: IsTraversableLike[That] { type A = B }): That = 
      xs.flatMap { a => itl.conversion(xs.map(f(a, _)))
  } 
}

Another option is to leave out IsTraversableLike completely:

import collection.GenTraversableOnce

implicit class CanCrossMap[A, Repr](xs: GenTraversableLike[A, Repr]) {
  def crossMap[B, That <: GenTraversableOnce[B]](f: (A, A) => B)(
    implicit cbf: CanBuildFrom[Repr, B, That]): That = 
      xs.flatMap { a => xs.map(f(a, _))}
}

Example:

Vector((1.0, 2.0), (3.0, 4.0), (5.0, 6.0)).crossMap { case ((ax, ay), (bx, by)) =>
  val dx = bx - ax
  val dy = by - ay
  math.sqrt(dx*dx + dy*dy)
}

Miles answer covers a few extra cases, where the collection is not directly a GenTraversableLike, namely Array and String (try substituting Vector for Array in the last example).

How can I add cross product based methods to scala collections?

2 Answers2