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?

Methylnaphthalene

Sounds like a job for index.scala-lang.org/slamdata/matryoshka/matryoshka-core/0.18.3 – Cauthen

The diagrams alone are worth checking matryoshka! – Laurettalaurette

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 ;-)

Geniculate

Answer 2

The way this is typically done is by defining an abstract class that contains all the functionality that you would want related to this recursive type, but does not actually take any constructor arguments. Rather, all of its methods take (at least one of) the type as an argument. The canonical example would be Ordering. Define one or more implicit implementations of this class, and then any time you need to use it, accept it as an implicit parameter. The corresponding example would be List's sorted method.

In your case, this might look like:

abstract class ArrayPrinter[A] {
  def mkString(a: A): String
}
implicit object BaseArrayPrinter extends ArrayPrinter[Int] {
  override def mkString(x: Int) = x.toString
}
class WrappedArrayPrinter[A](wrapped: ArrayPrinter[A]) extends ArrayPrinter[Array[A]] {
  override def mkString(xs: Array[A]) = xs.map(wrapped.mkString).mkString(", ")
}
implicit def makeWrappedAP[A](implicit wrapped: ArrayPrinter[A]): ArrayPrinter[Array[A]] = new WrappedArrayPrinter(wrapped)

def printHello[A](xs: A)(implicit printer: ArrayPrinter[A]): Unit = {
  println("hello, array: " + printer.mkString(xs))
}

This tends to be a bit cleaner than having that RAIOps class (or ArrayPrinter) take in an object as part of its constructor. That usually leads to more "boxing" and "unboxing", complicated type signatures, strange pattern matching, etc.

It also has the added benefit of being easier to extend. If later someone else has a reason to want an implementation of ArrayPrinter for a Set[Int], they can define it locally to their code. I have many times defined a custom Ordering.

Plane