Enrich-My-Library For all Traversables

Question

I was trying to figure out how to write a functional swap function that works on any Traversable[_], given a collection and the indexes to swap. I came up with the following:

def swap[A, CC <% Traversable[A]](xs: CC, i: Int, j: Int): Traversable[A] = {
  xs.slice(0, i) ++ 
    xs.slice(j, j+1) ++ 
    xs.slice(i+1, j) ++ 
    xs.slice(i, i+1) ++ 
    xs.slice(j+1, xs.size)
}

swap(List(1,2,3,4,5), 0, 4) // => List(5,2,3,4,1)

I'd like to know how to make this into an implicit extension of Traversable, enabling me to call it with List(1,2,3,4,5).swap(0, 4). The closest I could get was the following:

import language.implicitConversions
class RichTraversable[A, B <% Traversable[A]](xs: B) {
  def swap(i: Int, j: Int): Traversable[A] = {
    xs.slice(0, i) ++ 
      xs.slice(j, j+1) ++ 
      xs.slice(i+1, j) ++ 
      xs.slice(i, i+1) ++ 
      xs.slice(j+1, xs.size)
  }
} 
implicit def richTraversable[A, B <% Traversable[A]](ys: B)(implicit b: Traversable[A])
  = new RichTraversable[A, B](ys)

Unfortunately that's not quite it. Calling List(1,2,3,4,5).swap(0, 4) results in the following error:

error: No implicit view available from List[Int] => Traversable[A]

I feel I must be missing something, or vastly over-complicating the issue. Does anyone know how this should be structured?

---

Note: This is purely academic, and not being used in a production environment in any way. I'm trying to get a better handle on Scala's type system and bounds.

Nitriding

Answer 1

If you're using Scala 2.10:

import scala.collection.generic.CanBuildFrom
import scala.collection.TraversableLike

implicit class TraversableWithSwap[A, Repr <: Traversable[A]](val xs: TraversableLike[A, Repr]) extends AnyVal {
  def swap[That](i: Int, j: Int)(implicit bf: CanBuildFrom[Repr, A, That]): That = {
    val builder = bf(xs.asInstanceOf[Repr])
    builder.sizeHint(xs)
    builder ++= xs.take(i)
    builder ++= xs.slice(j, j + 1)
    builder ++= xs.slice(i + 1, j)
    builder ++= xs.slice(i, i + 1)
    builder ++= xs.drop(j + 1)
    builder.result
  }
}

(The AnyVal thing turns it into a Value Class, meaning that the compiler will rewrite it as a static function to avoid actually doing the wrapping during runtime.)

If using an earlier version, drop the extends AnyVal and use an implicit-conversion function instead of implicit class:

implicit def toTraversableWithSwap[A, Repr <: Traversable[A]](xs: TraversableLike[A, Repr]) = new TraversableWithSwap(xs)

And using it:

scala> Vector(1,2,3,4,5,6,7,8,9).swap(2,5)
res0: scala.collection.immutable.Vector[Int] = Vector(1, 2, 6, 4, 5, 3, 7, 8, 9)

Note that it doesn't actually make sense to define this function for all Traversable since some traversables (like Set, Map, etc) are unordered, so swapping two elements is meaningless. You probably would actually want to define it for all Seq or something.

Also: Can we also just agree to call it "enhance-my-library" already?

Harmon

First: Woah, what's this builder I've never seen before? And Second: Yes, we can agree to call it that from now on =) – Nitriding

The builder is what is used in the internal collections. See, for example: github.com/scala/scala/blob/master/src/library/scala/collection/… – Harmon

Hmm. I can't get it to find CanBuildFrom or TraversableLike. Is there an import I'm missing? – Nitriding

Yes, you'll have to import those. See my edit. By the way: if you need to locate a class to import, you can always find it in the API: scala-lang.org/api/current/index.html. – Harmon

Thanks. I did check out the API, but I somehow missed the line at the very top with the right package. I'd +1 you again, but alas, I cannot. – Nitriding