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

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

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 = ???) и т. д. и для всех из них должно быть выполнено условие (t: S): S .

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

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

Один из способов исправить assertNonNegative - написать честный мономорфный

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

другой - притвориться, что полиморфная подпись верна

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

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

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