Creating a method which takes any 2D sequence and turns it into an Array[Array[_]] in Scala

Question

As the title states, I want to have a method that can be applied to any kind of argument like Array[Array[_]] or Seq[Array[_]] or Array[Seq[_]] or Seq[Seq[_]]. The argument shall be turned into a 2D array (Array[Array[_]]), thus only changing the type of the collections involved.

I have the following signature seemingly accepting any such combination, but I can't build the Arrays.

  def apply[A: Manifest, S[_] <: Seq[_], U <% S[S[A]]](components: U): CombinationIterator[A] = {
    new CombinationIterator(Array(components.map((s: S[A]) => s.toArray)))
  }

The CombinationIterator class takes an Array[Array[T]] as its argument. I'm getting the following error:

error: could not find implicit value for evidence parameter of type ClassManifest[A]
new CombinationIterator(Array(components.map((s: S[A]) => s.toArray)))

For completeness, here is the constructor; maybe it matters, because it takes a Manifest for A.

class CombinationIterator[A: Manifest](components: Array[Array[A]]) extends Iterator[Array[A]]

a failing REPL session

The following works for Array[Seq[_]] but not for Seq[Array[_]]:

scala> def f[T:Manifest](s: Seq[Seq[T]]) = s.map(_.toArray).toArray
f: [T](s: Seq[Seq[T]])(implicit evidence$1: Manifest[T])Array[Array[T]]

scala> f(Array(Seq(1,2),Seq(3,4)))
res22: Array[Array[Int]] = Array(Array(1, 2), Array(3, 4))

scala> f(Seq(Array(1,2),Array(3,4)))
<console>:9: error: type mismatch;
 found   : Seq[Array[Int]]
 required: Seq[Seq[?]]
       f(Seq(Array(1,2),Array(3,4)))
            ^

(failing) REPL for didierd's idea

scala> def f[T: Manifest, ST <% Seq[T]](s: Seq[ST]) = s.map(_.toArray).toArray
f: [T, ST](s: Seq[ST])(implicit evidence$1: Manifest[T], implicit evidence$2: (ST) => Seq[T])Array[Array[T]]

scala> f(Seq(Seq(1)))
<console>:9: error: No implicit view available from Seq[Int] => Seq[T].
       f(Seq(Seq(1)))
        ^

Solution I've setted to

The following code works for my project. Maybe not all special cases are covered. This is a variant of Rex' second answer.

I feel that the implicits are nicely enclosed inside the companion object.

object CombinationIterator {
  case class AArray[T](aa: Array[Array[T]])
  implicit def seqseq2AA[T: Manifest](ss: Seq[Seq[T]]) = AArray(ss.map(_.toArray).toArray)
  implicit def seqarray2AA[T: Manifest](sa: Seq[Array[T]]) = AArray(sa.toArray)

  def apply[T: Manifest](components : AArray[T]): CombinationIterator[T] = {
    new CombinationIterator(components.aa)
  }
}

Edit

To post some newer insight about the reasons behind the question. I wanted to have these nested arrays because of performance reasons. But arrays are more important for primitive types. So it's probably not that bad - from a performance perspective - to have the outer array as a "proper" data structure, like a Vector.

Answer 1

Okay, finally got something clean and simple which requires no new implicits, though this is sort of inefficient since it converts away from array to Seq just so it can convert back again. Or you can use one implicit to stay with arrays:

The implicit-free answer:

def ss2aa[A,B[_],C[_]](c: C[B[A]])(
  implicit b2seq: B[A] => Seq[A], c2seq: C[B[A]] => Seq[B[A]], ma: ClassManifest[A]
) = c2seq(c).map(b => b2seq(b).toArray).toArray

More efficient, with implicit:

implicit def seq2array[A: ClassManifest](sa: Seq[A]) = sa.toArray
def ss2aa[A,B[_],C[_]](c: C[B[A]])(
  implicit b2arr: B[A] => Array[A], c2arr: C[B[A]] => Array[B[A]], ma: ClassManifest[A]
) = c2arr(c).map(b2arr)

---

Older, clumsier, but probablypossibly more efficient answers:

To work properly, this apparently needs a fairly heavyweight solution. One way is to encode the type union of Array and Seq using Either:

implicit def ss2leftleft[A](ssa: Seq[Seq[A]]) = Left(Left(ssa))
implicit def sa2leftright[A](saa: Seq[Array[A]]) = Left(Right(saa))
implicit def as2rightleft[A](asa: Array[Seq[A]]) = Right(Left(asa))
implicit def aa2rightright[A](aaa: Array[Array[A]]) = Right(Right(aaa))
def ss2aa[A: Manifest](
  x: Either[Either[Seq[Seq[A]],Seq[Array[A]]],Either[Array[Seq[A]],Array[Array[A]]]]
) = x match {
  case Left(Left(y)) => y.map(_.toArray).toArray
  case Left(Right(y)) => y.toArray
  case Right(Left(y)) => y.map(_.toArray)
  case Right(Right(y)) => y
}

If you felt like it, you could of course define your own superclass and subclass wrappers that did the same thing. Probably safer than using Either.

Another option is to use Miles Sabin's type union operator. Working through the manifests is a little ugly; here's a version that is actually safe but the compiler doesn't know it so casting is necessary:

object Example {
  // Type union system from Miles Sabin (with non-Unicode names)
  type Not[A] = A => Nothing
  type Union[A,B] = Not[Not[A] with Not[B]]
  type Id[A] = Not[Not[A]]

  def ss2aa[A,B[_],C[_]](b: C[B[A]])(
    implicit ev: (Id[B[A]] <:< Union[Seq[A],Array[A]]),
    ev2: (Id[C[B[_]]] <:< Union[Seq[B[_]],Array[B[_]]]),
    ma: ClassManifest[A],
    mssa: ClassManifest[Seq[Seq[A]]],
    msaa: ClassManifest[Seq[Array[A]]],
    masa: ClassManifest[Array[Seq[A]]],
    mf: ClassManifest[C[B[A]]]
  ) = {
    if (mf <:< mssa) b.asInstanceOf[Seq[Seq[A]]].map(_.toArray).toArray
    else if (mf <:< masa) b.asInstanceOf[Array[Seq[A]]].map(_.toArray)
    else if (mf <:< msaa) b.asInstanceOf[Seq[Array[A]]].toArray
    else b.asInstanceOf[Array[Array[A]]]
  }
}

Overall, I'd say the first solution is a little cleaner.