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.

Answer 2

An important part of your problem is that Array is implicitely convertible to Seq, but isnot a Seq (defined in the JVM, too late to add ancestors now).

In your first problem, you don't need your generic parameters to be that complex, and you might be pushing the type inference of scala beyond its capabilities. I can not tell you exactly where. The following signature should be enough :

def apply[A : Manifest, SA  <% Seq[A]](components: Seq[SA])

1. No need to find a common type for the outer and inner Seq type. So S: Seq[_] is useless.
2. You don't care what the outer type is, all that you do is Seq operation on it, Seq is enough. implicit conversions will work too, so an outer array wçll be fine.
3. As Seq is covariant, and your operation on the inner type are Seq operations too. Seq[Seq[A]] could be enough. But you want to accept Array at this point, hence S <% Seq[A] to allow the implicit conversion.

Beside that, you forgot the : _* in Array(components.map((s: S[A]) => s.toArray): _*). You must state it explicitely when you pass a Seq in place of repeated arguments.

With function F, the problem is again that Array is not a Seq. Same solution :

def f[T: Manifest, ST <% Seq[T]](s: Seq[ST])

Edit: Does not work. One has to pass the generic parameter explictely, scala cannot infer them.

A possible progress, but not a solution. With this you have only to state the type of the items, not the type of the inner Seq. I hope that someone will come with a better answer.

class NestedSeqToNestedArray[A : Manifest] {
   def on[SA <% Seq[A]](s: Seq[SA]) = s.map(_.toArray).toArray
}
object NestedSeqToNestedArray {
  def apply[A : Manifest] = new NestedSeqToNestedArray[A]
}

NestedSeqToNestedArray[Int].on(Seq(Array(1)))
res11: Array[Array[Int]] = Array(Array(1))

You cannot event call the "on" method apply (well you can but you have to write apply then) because if you pass an argument just after NestedSeqToNestedArray, it expect it to be the implicit Manifest.

Maybe worth mentionning, the trivial solution, define two functions ?

def f[A : Manifest](s: Seq[Seq[A]]) = s.map(_.toArray).toArray
def g[A : Manifest](s: Seq[Array[A]]) = s.map(_.clone).toArray