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

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

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

Есть ли какая-либо амбициозность в приведенном выше утверждении? (т.е. возможен ли какой-либо другой тип, кроме Int?)

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

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

[EDIT:] Компилятор достаточно умен, чтобы понять, что 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

Ответ 1

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

Однако в ситуации вроде

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

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

Ответ 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 type
error

если вы сделали if по-другому:

What is the type of expression "if (i <= 0) 0 else foo(i - 1) + 1 "?
Unify "0" and "foo(i - 1) + 1"
What is the type of "0"?
"0" <: Int >: Nothing
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 type
error