Scala recursive type and type constructor implementation

Question

I have a situation where I need a method that can take in types:

Array[Int]
Array[Array[Int]]
Array[Array[Array[Int]]]
Array[Array[Array[Array[Int]]]]
etc...

let's call this type RAI for "recursive array of ints"

def make(rai: RAI): ArrayPrinter = { ArrayPrinter(rai) }

Where ArrayPrinter is a class that is initialized with an RAI and iterates through the entire rai (let's say it prints all the values in this Array[Array[Int]])

val arrayOfArray: Array[Array[Int]] = Array(Array(1, 2), Array(3, 4))
val printer: ArrayPrinter[Array[Array[Int]]] = make(arrayOfArray)
printer.print_! // prints "1, 2, 3, 4" 

It can also return the original Array[Array[Int]] without losing any type information.

val arr: Array[Array[Int]] = printer.getNestedArray() 

How do you implement this in Scala?

Answer 1

Let's first focus on type. According to your definition, a type T should typecheck as an argument for ArrayPrinter is it accepted by the following type function:

def accept[T]: Boolean =
  T match { // That's everyday business in agda
    case Array[Int] => true
    case Array[X]   => accept[X]
    case _          => false
  }

In Scala, you can encode that type function using implicit resolution:

trait RAI[T]

object RAI {
  implicit val e0: RAI[Array[Int]] = null
  implicit def e1[T](implicit i: RAI[T]): RAI[Array[T]] = null
}

case class ArrayPrinter[T: RAI](getNestedArray: T) // Only compiles it T is a RAI

To print things the simplest solution is to treat the rai: T as a rai: Any:

def print_!: Unit = {
  def print0(a: Any): Unit = a match {
    case a: Int      => println(a)
    case a: Array[_] => a.foreach(print0)
    case _           => ???
  }
}

You could also be fancy and write print_! using type classes, but that would probably be less efficient and take more time to write than the above... Left as an exercise for the reader ;-)