Tuesday, October 4, 2011

Generic operations on scala collections - Using builders

Scala collections are very impressive, they achieve a high degree of genericity, a single method can be applied on any kind of collections ! Let's see an example through an operation consisting on removing identical consecutives elements.

Let's see a first simple implementation :
def compact[A](list:List[A]):List[A] = {
  var buf  = collection.mutable.ListBuffer.empty[A]
  var prev:Option[A] = None
  for(item <- list) {
    if (prev==None || prev.get!=item) buf += item
    prev=Some(item)
  }
  buf.toList
}

Or using folding :
def compact[A](list:List[A]):List[A] = {
  (List[A]() /: list) { (nl, I) => nl.headOption match { 
      case Some(I) => nl
      case Some(_)|None=> I::nl
    }
  } reverse
}

The problem with those implementations is that the collection type is "hardcoded", if you need to realize the same operation on Queues, Stacks, Vectors,... you will have to provide as many implementations as you have collections types you want to be taken into account by a compact operation.
You'll first thing that's this is not a problem, you just have to parameterize not only the item type but also the collection type using such method declaration :
def compact[A, I[A]<:Iterable[A]](list:I[A]) : I[A] = {
   ...
}

But such approach is a dead end issue, because you need to create a new collection of type I[A] which should inheritate from Iterable[A], but of course it is not possible to create such instance from type parameter. Trying, I.empty[A] or I[A]() won't work and will generate compiler error.

Scala provides an elegant solution based on implicits builders, in fact all collections provides builders that we're free to reuse in order to implement generic operations on collections.
// Fully generic implementation using collection builder
def compact[A, I[A]<:Iterable[A]](list:I[A]) (implicit bf: CanBuildFrom[I[A], A, I[A]]) : I[A] = {
  var builder = bf.apply()
  var prev:Option[A]=None
  for(item <- list) {
    if (prev==None || prev.get != item) builder += item
    prev=Some(item)
  }
  builder.result
}

Here find the complete example ready to run and test :
#!/bin/sh
exec scala -deprecation -savecompiled "$0" "$@"
!#
import scala.collection._
import scala.collection.immutable.{Queue,Stack}
import scala.collection.generic.CanBuildFrom

// Simple implementation
def compact0[A](list:List[A]) = {
  var buf  = collection.mutable.ListBuffer.empty[A]
  var prev:Option[A] = None
  for(item <- list) {
    if (prev==None || prev.get!=item) buf += item
    prev=Some(item)
  }
  buf.toList
}

// A bad recursive implementation
def compact1[A](list:List[A], prev:Option[A]=None):List[A] = {
  list match {
    case Nil => Nil
    case that::remain if (prev == None || prev.get != that) => that::compact1(remain, Some(that))
    case that::remain => compact1(remain, Some(that))
  }
}

// Implementation using folding
def compact2[A](list:List[A]):List[A] = {
  (List[A]() /: list) { (nl, I) => nl.headOption match { 
      case Some(I) => nl
      case Some(_)|None=> I::nl
    }
  } reverse
}

// Implementation using folding and a dedicated test function
def compactT1[A](list:List[A], tst:(A,A)=>Boolean):List[A] = {
  (List[A]() /: list) { (nl, i) => nl.headOption match { 
      case Some(iprev) if tst(iprev,i) => nl 
      case Some(_)|None=> i::nl
    }
  } reverse
}


// Fully generic implementation using builder
def compact[A, I[A]<:Iterable[A]](list:I[A])(implicit bf: CanBuildFrom[I[A], A, I[A]]):I[A] = {
  var builder = bf.apply()
  var prev:Option[A]=None
  for(item <- list) {
    if (prev==None || prev.get != item) builder += item
    prev=Some(item)
  }
  builder.result
}


// Fully generic implementation using builder and dedicated test function
def compactT[A, I[A]<:Iterable[A]](list:I[A], tst:(A,A)=>Boolean)
          (implicit bf: CanBuildFrom[I[A], A, I[A]]):I[A] = {
  var builder = bf.apply()
  var prev:Option[A]=None
  for(item <- list) {
    if (prev==None || !tst(prev.get,item)) builder += item
    prev=Some(item)
  }
  builder.result
}


// ----------------------------------
assert(compact(List.empty) == List())

// ----------------------------------
val l1 = List(1,1,1,2,3,3,2,2,2,4,4,1,1)
val l1compacted = List(1,2,3,2,4,1)
assert(compact0(l1) == l1compacted)
assert(compact1(l1) == l1compacted)
assert(compact2(l1) == l1compacted)
assert(compact(l1) == l1compacted)


// ----------------------------------
case class Cell(t:Int, v:Int)
val l2=List(Cell(1,10), Cell(2,11), Cell(2,4), Cell(3,1), Cell(3,2), Cell(2,0), Cell(2,30))
val l2compacted= List(Cell(1,10), Cell(2,11), Cell(3,1), Cell(2,0))
assert(compactT1(l2,(x:Cell,y:Cell)=>x.t==y.t) == l2compacted)
assert(compactT(l2,(x:Cell,y:Cell)=>x.t==y.t) == l2compacted)

// ----------------------------------
val testcase=List(1,1,1,2,3,3,2,2,2,4,4,1,1)
val testresult=List(1,2,3,2,4,1)

// ----------------------------------
val v1 = Vector(testcase :_ *)
val v1compacted = Vector(testresult :_ *)
assert(compact(v1) == v1compacted)

// ----------------------------------
val s1 = Stack(testcase :_ *)
val s1compacted =Stack(testresult :_ *)
assert(compact(s1) == s1compacted)

// ----------------------------------
val q1 = Queue(testcase :_ *)
val q1compacted =Queue(testresult :_ *)
assert(compact(q1) == q1compacted)

// ----------------------------------
val ab1 = collection.mutable.ArrayBuffer(testcase :_ *)
val ab1compacted = collection.mutable.ArrayBuffer(testresult :_ *)
assert(compact(ab1) == ab1compacted)

// ----------------------------------
val sq1 = Seq(testcase :_ *)
val sq1compacted =Seq(testresult :_ *)
assert(compact(sq1) == sq1compacted)




1 comment:

  1. Good, but it needs a little bit more to work with collections that are not parameterized, such as Range.

    ReplyDelete