Можно ли расширить компилятор 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
