Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Enrich-My-Library For all Traversables

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.

like image 595
KChaloux Avatar asked Mar 29 '13 18:03

KChaloux


1 Answers

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?

like image 91
dhg Avatar answered Oct 04 '22 11:10

dhg