È possibile estendere il compilatore Scala per dedurre i tipi di ritorno dei metodi ricorsivi?

Il compilatore Scala attualmente non può dedurre i tipi di metodi ricorsivi come nel codice seguenteÈ possibile estendere il compilatore Scala per dedurre i tipi di ritorno dei metodi ricorsivi?

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

tornare C'è ambuigity nella dichiarazione di cui sopra? (cioè, è possibile qualsiasi altro tipo oltre allo Int?)

Posso immaginare che in un esempio più complesso, sarà difficile dedurne il tipo.

È possibile caratterizzare ulteriormente i casi di metodi ricorsivi in cui possiamo (non) dedurre i tipi?

[EDIT:] Il compilatore è abbastanza intelligente da capire che String non è corretto.

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

fonte

2011-10-11 Jus12

Credo 'Double' è un altro tipo possibile. – Jus12

http://stackoverflow.com/questions/3739133/why-does-scala-require-a-return-type-for-recursive-functions/3739174#3739174 – retronym

@ Jus12 'foo: Double' è possibile proprio come è possibile dichiarare 'def f = 2' come': Double'. Tuttavia, il compilatore deduce che 'def f = 2' sia un': Int'. Un inferrer di tipo ricorsivo sensibile non assumerebbe 'foo: Double' per la stessa ragione nel tuo esempio. – Debilski

Se la chiamata ricorsiva è sempre in ultima posizione, vale a dire il suo valore non viene mai utilizzato e restituito solo, dovrebbe essere possibile determinare il tipo come il supertipo comune di tutte le altre branche.

Tuttavia, in una situazione come

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

non si sa il tipo di foo(i - 1) + 1 (o capire il funzionamento + perché in realtà è un metodo su foo - le cose sono sempre più complicate in presenza di oggetti) senza sapere cosa sia foo. Quindi, di nuovo ti stai muovendo in tondo.

fonte

2011-10-11 21:56:59 Debilski

Avresti bisogno di un algoritmo di unificazione molto più potente di quello fornito da Scala. Scala esegue il controllo da sinistra a destra, dall'alto verso il basso. Così l'inferenza sarebbe un po 'come questo:

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

se avete fatto l'if il contrario si avrebbe:

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's type 
error

fonte

2011-10-12 22:46:20

Una buona spiegazione di come il compilatore Scala dia i tipi. – Jus12

È possibile estendere il compilatore Scala per dedurre i tipi di ritorno dei metodi ricorsivi?

risposta

Problemi correlati