Given the following List:
val l = List(List(1, 2, 3), List(4, 5), List(6, 7, 8))
If I try to transpose it, Scala will throw the following error:
scala> List.transpose(l)
java.util.NoSuchElementException: head of empty list
at scala.Nil$.head(List.scala:1365)
at scala.Nil$.head(List.scala:1362)
at scala.List$$anonfun$transpose$1.apply(List.scala:417)
at scala.List$$anonfun$transpose$1.apply(List.scala:417)
at scala.List.map(List.scala:812)
at scala.List$.transpose(List.scala:417)
at .<init>(<console>:6)
at .<clinit>(<console>)
at RequestResult...
This is because List.transpose assumes equal-length lists and so uses the head method:
def transpose[A](xss: List[List[A]]): List[List[A]] = {
val buf = new ListBuffer[List[A]]
var yss = xss
while (!yss.head.isEmpty) {
buf += (yss map (_.head))
yss = (yss map (_.tail))
}
buf.toList
}
I would like to get the following:
List(List(1, 4, 6), List(2, 5, 7), List(3, 8))
Is writing my own version of transpose the best way to do this? This is what I came up with:
def myTranspose[A](xss: List[List[A]]): List[List[A]] = {
val buf = new ListBuffer[List[A]]
var yss = xss
while (!yss.head.isEmpty) {
buf += (yss filter (!_.isEmpty) map (_.head))
yss = (yss filter (!_.isEmpty) map (_.tail))
}
buf.toList
}
Update: I was interested in comparing the speed of the different solutions offered here, so I put together the following little benchmark:
import scala.testing.Benchmark
import scala.collection.mutable.ListBuffer
trait Transpose extends Benchmark {
def transpose[Int](xss: List[List[Int]]): List[List[Int]] = Nil
val list: List[List[Int]] = List(List(1,2,3), Nil, List(4,5,99,100), List(6,7,8))
def run = {
val l = transpose(list)
println(l)
l
}
}
object PRTranspose extends Transpose {
override def transpose[Int](xss: List[List[Int]]): List[List[Int]] = {
val buf = new ListBuffer[List[Int]]
var yss = xss
while (!yss.head.isEmpty) {
buf += (yss filter (!_.isEmpty) map (_.head))
yss = (yss filter (!_.isEmpty) map (_.tail))
}
buf.toList
}
}
object ACTranspose extends Transpose {
override def transpose[Int](xss: List[List[Int]]): List[List[Int]] = {
val b = new ListBuffer[List[Int]]
var y = xss filter (!_.isEmpty)
while (!y.isEmpty) {
b += y map (_.head)
y = y map (_.tail) filter (!_.isEmpty)
}
b.toList
}
}
object ETranspose extends Transpose {
override def transpose[Int](xss: List[List[Int]]): List[List[Int]] = xss.filter(!_.isEmpty) match {
case Nil => Nil
case ys: List[List[Int]] => ys.map{ _.head }::transpose(ys.map{ _.tail })
}
}
My commands were:
scala PFTranspose 5 out.log
scala ACTranspose 5 out.log
scala ETranspose 5 out.log
My results were:
PRTranspose$ 10 0 1 1 0
ACTranspose$ 9 2 0 0 0
ETranspose$ 9 3 2 3 1