Можно ли расширить компилятор Scala, чтобы выводить возвращаемые типы рекурсивных методов?

Question

Компилятор Scala в настоящее время не может определить типы возвращаемых данных рекурсивных методов, как показано в следующем коде

def foo(i:Int) = if (i > 0) foo (i-1) else 0

Есть ли двусмысленность в приведенном выше утверждении?(т. е. возможен ли любой тип, отличный от Int?)

Я могу представить, что в более сложном примере будет сложно вывести тип.

Можно ли дополнительно охарактеризовать случаи рекурсивных методов, когда мы можем (не) выводить типы?

[ПРАВИТЬ:] Компилятор достаточно умен, чтобы выяснить, что Stringневерно.

scala> def foo(i:Int):String = if (i > 0) foo (i-1) else 0
<console>:5: error: type mismatch;
found   : Int(0)
required: String

Answer 1

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

Однако вВ такой ситуации, как

def foo(i: Int) = if (i > 0) foo(i - 1) + 1 else 0

, вы не знаете тип foo(i - 1) + 1 (или не понимаете операцию +, потому что на самом деле это метод foo - все становится сложнее в присутствииобъекты), не зная, что такое foo.Итак, вы снова двигаетесь кругами.

Answer 2

Вам потребуется алгоритм объединения, гораздо более мощный, чем тот, который предоставляет Scala.Scala выполняет проверку типов слева направо, сверху вниз.Таким образом, вывод будет выглядеть примерно так:

What is the type of expression "if (i > 0) foo(i - 1) + 1 else 0"?
Unify "foo(i - 1) + 1" and "0"
What is the type of "foo(i - 1) + 1"?
What is the type of "foo(i - 1)"
What is "foo"?
foo is the current definition, so we don't know it's type
error

, если бы вы сделали if в обратном направлении, у вас было бы: