Как указать тип возвращаемого значения для вложенных массивов произвольной длины вложенности?

Question

Предположим, в качестве примера, я хочу функцию, которая рекурсивно оборачивает массив в другой массив, n раз.

Другими словами, желаемый результат:

wrap(Array(1,2,3), 2) = Array(Array(Array(1,2,3)))
wrap(Array(4,5,6), 3) = Array(Array(Array(Array(4,5,6))))

Как указать тип возвращаемого значения? Это зависит от n. Предполагая, что вход имеет тип Array[A]:

Для n=1, это Array[Array[A]].

Для n=3, это Array[Array[Array[Array[A]]]]

Мы могли бы использовать Array[_] как:

def wrap[A:ClassTag](x:Array[A], n:Int):Array[_] = { 
  if (n == 1) {
    Array(x)
  } else {
    wrap(Array(x), n-1)
  }
}

но тогда компилятор не знает, что элементы Array s:

> val y = wrap(Array(1,2,3), 1)
  Array[_] = Array(Array(1, 2, 3))
> y(0).length
error: value length is not a member of _$1
  y(0).length
       ^

Мы можем использовать asInstanceOf, но это не похоже на отличное решение:

> y(0).asInstanceOf[Array[Int]].length
  Int = 3

Answer 1

Я не думаю, что идеальное решение возможно, так как значение n определяется во время выполнения, но тип возвращаемого значения должен присутствовать во время компиляции. Если n никогда не является литералом, как в ваших примерах, то, вероятно, лучшее, что вы можете сделать, это вернуть Array[_].

Но если вы всегда собираетесь использовать литерал, вы можете по существу передать n во время компиляции в качестве параметра типа. Вместо прохождения n=1 вы передаете A=Array[Array[Int]]:

import scala.reflect.ClassTag

trait Wrapper[A, B] {
  def wrap(xs: Array[B]): A
}

implicit def wrapperBase[B] = new Wrapper[Array[B], B] {
  def wrap(xs: Array[B]) = xs
}

implicit def wrapperRec[A : ClassTag, B](implicit w: Wrapper[A, B]) = new Wrapper[Array[A], B] {
  def wrap(xs: Array[B]): Array[A] = Array(w.wrap(xs))
}

def wrap[B, A](xs: Array[B])(implicit w: Wrapper[A, B]): A = w.wrap(xs)

val xs = Array(1, 2, 3)
wrap[Int, Array[Array[Int]]](xs)  // instead of wrap(xs, 1)
wrap[Int, Array[Array[Array[Int]]]](xs)  // instead of wrap(xs, 2)

Если вы хотите получить действительно фантазию, вы можете получить целочисленные типы во время компиляции класса ala shapeless Nat и теоретически делать такие вещи, как wrap[Int, _5], но это определенно большая кроличья нора для небольшой выгоды .

Answer 2

Невозможно сделать это простым способом. Типы являются гражданами во время компиляции, а числа живут во время выполнения. Посмотрим, что произойдет, если число n будет считано с пользовательского ввода. Для разных будущих пользовательских вводов компилятор должен генерировать разные типы результатов для метода.

Если я не ошибаюсь, для этого нам понадобится язык с лучшей поддержкой зависимых типов, чем Scala. Смотрите этот вопрос: Любая причина, почему Scala не поддерживает явно зависимые типы? и особенно ответ П. Фролова там.

Тем не менее, можно выразить этот тип, если число n известно во время компиляции. Например, это литерал Int, final val или какое-то простое арифметическое выражение литералов и final val s. Например, в случае final val a = 3; wrap(Array(1,2,3), a * 2 + 1).

Вот пример кода класса типов, который реализует эту упаковку. Он использует библиотеку shapeless для удобного преобразования числовых литералов в Nat значения типа:

import scala.reflect.{classTag, ClassTag}

abstract class Wrapper[T : ClassTag, N <: Nat] {
  // Type of Array[T] wrapped N times
  type Out 

  // ClassTag of the array wrapped N times. 
  // It's needed to be able to wrap it one more time.
  def outTag: ClassTag[Out]

  // The actual function that wraps the array
  def apply(array: Array[T]): Out 
}

object Wrapper {
  type Aux[T, N <: Nat, O] = Wrapper[T, N] { type Out = O }

  // Wrap the array 0 times. The base of the recursion.
  implicit def zero[T : ClassTag]: Aux[T, Nat._0, Array[T]] = new Wrapper[T, Nat._0] {
    type Out = Array[T]
    def outTag = classTag[T].wrap
    def apply(array: Array[T]): Out = array
  }

  // Given a Wrapper, that wraps the array N times,
  //   make a Wrapper, that wraps N + 1 times.
  implicit def next[T : ClassTag, N <: Nat](
    implicit prev: Wrapper[T, N]
  ): Aux[T, Succ[N], Array[prev.Out]] = new Wrapper[T, Succ[N]] {
    type Out = Array[prev.Out]
    def outTag = prev.outTag.wrap
    def apply(array: Array[T]): Out = Array(prev(array))(prev.outTag)
  }
}

И функция обтекания, которая использует этот класс типов:

def wrap[A: ClassTag](
  x: Array[A], 
  n: Nat
)(
  implicit wrapper: Wrapper[A, n.N]
): wrapper.Out = 
  wrapper(x)

Компилятор знает тип результата и может использовать результат без каких-либо типов:

scala> val a = wrap(Array(1,2,3), 3)
a: Array[Array[Array[Array[Int]]]] = Array(Array(Array(Array(1, 2, 3))))

scala> a.head.head.head.sum
res1: Int = 6

scala> object Foo {
  final val n = 2
  def run() = wrap(Array(1,2,3), n * 2 + 1)
} 
defined object Foo

scala> Foo.run()
res2: Array[Array[Array[Array[Array[Array[Int]]]]]] = Array(Array(Array(Array(Array(Array(1, 2, 3))))))

Answer 3

Array[_] - правильный тип для такого метода, но не вся информация о типах была потеряна. Вы можете использовать сопоставление с образцом, чтобы получить его.

def unwrap(a :Array[_]) :String = a match {
  case Array(sa :Array[_]) => unwrap(sa)
  case ia :Array[Int]      => ia.mkString("+")
  case x                   => x.mkString("-")
}

При этом лучше вообще избегать произвольных вложенных типов.