Почему я не могу вернуть конкретный подтип A, если подтип generi c из A объявлен как возвращаемый параметр? - PullRequest
Новая
       59

Почему я не могу вернуть конкретный подтип A, если подтип generi c из A объявлен как возвращаемый параметр?

1 голос
/ 08 мая 2020 
abstract class IntTree
object Empty extends IntTree
case class NonEmpty(elem: Int, left: IntTree, right: IntTree) extends IntTree

def assertNonNegative[S <: IntTree](t: S): S = {
  t match {
    case Empty => Empty  // type mismatch, required: S, found: Empty.type
    case NonEmpty(elem, left, right) =>
      if (elem < 0) throw new Exception
      else NonEmpty(elem, assertNonNegatve(left), assertNonNegative(right)) // req: S, fd: NonEmpty.type
  }
}

Это моя неудачная попытка реализовать функцию с сигнатурой def assertNonNegative[S <: IntTree](t: S): S. Кроме изменения подписи на def assertNonNegative(t: IntTree): IntTree, мне не удалось найти способ реализовать это.

Актуальность примера: В видеоролике о подтипах и дженериках (4.4) в курсе «Принципы функционального программирования в Scala» Мартин Одерски использует практически тот же пример (IntSet вместо IntTree) и говорит, что эта сигнатура может использоваться для express, что функция переводит Empty в Empty и NonEmpty в NonEmpty. Он говорит, что в большинстве ситуаций подходит другая подпись, но при необходимости подпись с ограниченным сверху S может быть более точным вариантом. Однако он не показывает реализацию функции.

Что мне здесь не хватает?

1 Ответ

5 голосов
/ 08 мая 2020

Правая сторона метода (сопоставление с образцом) 

t match {
  case Empty => Empty 
  case NonEmpty(elem, left, right) =>
    if (elem < 0) throw new Exception
    else NonEmpty(elem, assertNonNegatve(left), assertNonNegative(right)) 
}

означает проверку во время выполнения, является ли t экземпляром класса Empty$ (объект Empty), а затем выберите первую ветвь или в противном случае, является ли t экземпляром класса NonEmpty, а затем выберите вторую ветвь.

Подпись 

def assertNonNegative[S <: IntTree](t: S): S

означает проверку во время компиляции, что для каждого типа S, который является подтипом типа IntTree, если метод принимает параметр t типа S, тогда метод возвращает значение типа S.

Код не компилируется из-за определения метод не соответствует его сигнатуре. Подклассами IntTree являются NonEmpty и Empty (объект). Если IntTree не запечатано, вы можете создавать его подклассы, отличные от Empty и NonEmpty, вы даже можете создавать их динамически во время выполнения. Но давайте даже предположим, что IntTree запечатан, а Empty и NonEmpty - его единственные подклассы.

Дело в том, что существует множество подтипов IntTree (классы и типы разные ): IntTree, Empty.type, NonEmpty, Nothing, Null, Empty.type with NonEmpty, NonEmpty with SomeType, Empty.type with SomeType, IntTree with SomeType, T (type T <: IntTree ), x.type (val x: IntTree = ???) и c. и для всех должно выполняться условие (t: S): S.

Очевидно, что это не так. Например, можно взять t = Empty.asInstanceOf[Empty.type with Serializable]. Имеет тип Empty.type with Serializable. Во время выполнения он соответствует классу Empty (объект), поэтому выбирается первая ветвь. Но во время компиляции мы этого еще не знаем, как вы можете гарантировать, что во время компиляции оба возвращенных Empty и NonEmpty имеют тип Empty.type with Serializable?

Несоответствие типов в аннотации тип, используемый в сопоставлении с образцом

Один из способов исправить assertNonNegative - написать честные monomorphi c

def assertNonNegative(t: IntTree): IntTree = {
  t match {
    case Empty => Empty
    case NonEmpty(elem, left, right) =>
      if (elem < 0) throw new Exception
      else NonEmpty(elem, assertNonNegative(left), assertNonNegative(right))
  }
}

, другой - притвориться, что polymorphi c подпись верна 

def assertNonNegative[S <: IntTree](t: S): S = {
  (t match {
    case Empty => Empty
    case NonEmpty(elem, left, right) =>
      if (elem < 0) throw new Exception
      else NonEmpty(elem, assertNonNegative(left), assertNonNegative(right))
  }).asInstanceOf[S]
}

третий - использовать теги типов 

def assertNonNegative[S <: IntTree : TypeTag](t: S): S = {
  t match {
    case Empty if typeOf[S] == typeOf[Empty.type] => Empty.asInstanceOf[S]
    case NonEmpty(elem, left, right) if typeOf[S] == typeOf[NonEmpty] =>
      if (elem < 0) throw new Exception
      else NonEmpty(elem, assertNonNegative(left), assertNonNegative(right)).asInstanceOf[S]
    case _ => ???
  }
}

четвертый - сделать ADT более типовым 

sealed trait IntTree
object Empty extends IntTree
case class NonEmpty[L <: IntTree, R <: IntTree](elem: Int, left: L, right: R) extends IntTree

и определить класс типа 

def assertNonNegative[S <: IntTree](t: S)(implicit ann: AssertNonNegative[S]): S = ann(t)

trait AssertNonNegative[S <: IntTree] {
  def apply(t: S): S
}
object AssertNonNegative {
  implicit val empty: AssertNonNegative[Empty.type] = { case Empty => Empty }
  implicit def nonEmpty[L <: IntTree : AssertNonNegative, 
                        R <: IntTree : AssertNonNegative]: AssertNonNegative[NonEmpty[L, R]] = {
    case NonEmpty(elem, left, right) =>
      if (elem < 0) throw new Exception
      else NonEmpty(elem, assertNonNegative(left), assertNonNegative(right))
  }
}

Надежность системы типов означает, что иногда мы отклоняем некоторые программы во время компиляции, в то время как они не могут go ошибаться во время выполнения. Например 

val x: Int = if (true) 1 else "a"
...