Array.map returns ArraySeq?

Question

I am making a small example of a linear algebra with sequential and parallel implementations. Below is the current code:

import util.Random
import System.currentTimeMillis
import actors.Futures._
import Numeric.Implicits._

object Parallel extends App{

  val rnd = new Random(1337)//Seeded RNG

  //Create 2 matrices with dimension NxN
  val N = 550
  val A:Array[Array[Double]] = Array.fill(N,N){ rnd.nextDouble }
  val B:Array[Array[Double]] = Array.fill(N,N){ rnd.nextDouble }

  //Time a call-by-name block and return milli-seconds
  def time(b: => Unit):Long = {
    val start = currentTimeMillis
    b
    currentTimeMillis-start
  }


  val sequentialProgram = new LinearAlgebra with SequentialLinearAlgebra {
    println("Sequential time: "+time { A * B } )
  }

  val parColProgram = new LinearAlgebra with ParColLinearAlgebra {
    println("ParCol time: "+time { A * B } )
  }

  val futureProgram = new LinearAlgebra with FutureLinearAlgebra {
    println("Future time: "+time { A * B } )
  }

}

//Interface, knows nothing about implementation
trait LinearAlgebra{

  type Vector[T] = Array[T]
  type Matrix[T] = Vector[Vector[T]]

  implicit class VectorOps[T:Numeric](v:Vector[T]){
    def dot(that:Vector[T]):T = innerProd(v,that)
  }
  implicit class MatrixOps[T:Numeric](m:Matrix[T]){
    def *(that:Matrix[T]):Matrix[T] = matMul(m,that)
  }

  //Functionality is deferred to implementing traits
  def innerProd[T:Numeric](a:Vector[T],b:Vector[T]):T
  def matMul[T:Numeric](A:Matrix[T],B:Matrix[T]):Matrix[T]
}

//Implements LinearAlgebra interface in a sequential fashion
trait SequentialLinearAlgebra extends LinearAlgebra {

  def innerProd[T:Numeric](a:Vector[T],b:Vector[T]) =
    ((a,b).zipped map (_*_)).sum

  def matMul[T:Numeric](A:Matrix[T],B:Matrix[T]) = {
      val Bt = B.transpose      
      A.map(row => Bt.map(col => row dot col)) 
    }

}

//Implements LinearAlgebra interface using parallel collections
trait ParColLinearAlgebra extends LinearAlgebra {

  def innerProd[T:Numeric](a:Vector[T],b:Vector[T]) =
    ((a,b).zipped map (_*_)).sum

  def matMul[T:Numeric](A:Matrix[T],B:Matrix[T]) = {
    val Bt = B.transpose
    (A.par map (row => Bt map (col => row dot col))).toArray
  }

}

//Implements LinearAlgebra interface using futures, i.e. explicit workload distribution
trait FutureLinearAlgebra extends LinearAlgebra {

  def innerProd[T:Numeric](a:Vector[T],b:Vector[T]) =
    ((a,b).zipped map (_*_)).sum

  def matMul[T:Numeric](A:Matrix[T],B:Matrix[T]) = {
      val Bt = B.transpose
      val res = A map ( row => future {Bt map (col => row dot col)}) 
      res.map(_.apply)
    }

}

The code seems correct to me, but I get the following errors:

fsc Parallel.scala
/home/felix/Documents/teaching/2014/dm509/scala/Parallel.scala:61: error: type mismatch;
 found   : Array[scala.collection.mutable.ArraySeq[T]]
 required: SequentialLinearAlgebra.this.Matrix[T]
    (which expands to)  Array[Array[T]]
      A.map(row => Bt.map(col => row dot col)) 
           ^
/home/felix/Documents/teaching/2014/dm509/scala/Parallel.scala:71: error: type mismatch;
 found   : Array[scala.collection.mutable.ArraySeq[T]]
 required: ParColLinearAlgebra.this.Matrix[T]
    (which expands to)  Array[Array[T]]
    (A.par map (row => Bt map (col => row dot col))).toArray
                                                     ^
/home/felix/Documents/teaching/2014/dm509/scala/Parallel.scala:82: error: type mismatch;
 found   : Array[scala.collection.mutable.ArraySeq[T]]
 required: FutureLinearAlgebra.this.Matrix[T]
    (which expands to)  Array[Array[T]]
      res.map(_.apply)
             ^
three errors found

The problem seems to be that Array.map sometimes returns ArraySeq as oppposed to the expected Array. If I do a search-replace with Array and List, the program works as expected. The reason for moving to Array is that I wish to compare the efficiency to an imperative implementation, i.e., I need efficient random access. Can someone explain this behaviour?

Answer 1

The context bound makes the difference:

scala> val as = Array.tabulate(10,10)((x,y)=>y)
as: Array[Array[Int]] = Array(Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9))

scala> as map (x => x.sum)
res0: Array[Int] = Array(45, 45, 45, 45, 45, 45, 45, 45, 45, 45)

scala> def f[A: Numeric](as: Array[Array[A]]) = as map (x => x.sum)
f: [A](as: Array[Array[A]])(implicit evidence$1: Numeric[A])scala.collection.mutable.ArraySeq[A]

scala> def f[A](as: Array[Array[A]]) = as map (x => 42)
f: [A](as: Array[Array[A]])Array[Int]

Presumably it uses the fallback CanBuildFrom that yields a Seq.

Edit: to fix it, supply a reflect.ClassTag[T] so that it can create the Array[T] you want.

You'll need it on:

def matMul[T:Numeric](A:Matrix[T],B:Matrix[T])(implicit ev1: ClassTag[T])

and

implicit class MatrixOps[T:Numeric](m:Matrix[T])(implicit ev1: ClassTag[T])