Penso che ci sia l'annotazione @tailrec
per assicurare che il compilatore ottimizzi una funzione ricorsiva della coda. Lo metti di fronte alla dichiarazione? Funziona anche se Scala viene utilizzato in modalità di script (ad esempio utilizzando :load <file>
in REPL)?Che cos'è l'annotazione Scala per garantire che una funzione ricorsiva della coda sia ottimizzata?
Che cos'è l'annotazione Scala per garantire che una funzione ricorsiva della coda sia ottimizzata?
risposta
Dal post "Tail calls, @tailrec and trampolines" blog:
- In Scala 2.8, sarà anche in grado di utilizzare la nuova
@tailrec
di annotazione per ottenere informazioni su quali sono ottimizzati metodi.
Questa annotazione consente di contrassegnare metodi specifici che si spera che il compilatore ottimizzi.
Avrai quindi un avviso se non sono ottimizzati dal compilatore.- In Scala 2.7 o versioni precedenti, è necessario fare affidamento sul test manuale o sull'ispezione del bytecode per stabilire se un metodo è stato ottimizzato.
Esempio:
si potrebbe aggiungere un'annotazione
@tailrec
in modo che si può essere certi che le modifiche hanno funzionato.
import scala.annotation.tailrec
class Factorial2 {
def factorial(n: Int): Int = {
@tailrec def factorialAcc(acc: Int, n: Int): Int = {
if (n <= 1) acc
else factorialAcc(n * acc, n - 1)
}
factorialAcc(1, n)
}
}
E funziona dal REPL (ad esempio dalla Scala REPL tips and tricks):
C:\Prog\Scala\tests>scala
Welcome to Scala version 2.8.0.RC5 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_18).
Type in expressions to have them evaluated.
Type :help for more information.
scala> import scala.annotation.tailrec
import scala.annotation.tailrec
scala> class Tails {
| @tailrec def boom(x: Int): Int = {
| if (x == 0) throw new Exception("boom!")
| else boom(x-1)+ 1
| }
| @tailrec def bang(x: Int): Int = {
| if (x == 0) throw new Exception("bang!")
| else bang(x-1)
| }
| }
<console>:9: error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position
@tailrec def boom(x: Int): Int = {
^
<console>:13: error: could not optimize @tailrec annotated method: it is neither private nor final so can be overridden
@tailrec def bang(x: Int): Int = {
^
Il compilatore Scala ottimizzerà automaticamente qualsiasi metodo veramente ricorsivo alla coda. Se annoti un metodo che ritieni sia ricorsivo in coda con l'annotazione @tailrec
, il compilatore ti avviserà se il metodo non è effettivamente ricorsivo in coda. Ciò rende l'annotazione @tailrec
una buona idea, sia per garantire che un metodo sia attualmente ottimizzabile e che rimanga ottimizzato in quanto modificato.
Si noti che Scala non considera un metodo per essere ricorsivo in coda se può essere sovrascritto. Quindi il metodo deve essere privato, finale, su un oggetto (al contrario di una classe o tratto) o all'interno di un altro metodo da ottimizzare.
L'annotazione è scala.annotation.tailrec
. Si innesca un errore del compilatore se il metodo non può essere chiamata coda ottimizzata, che avviene se:
- La chiamata ricorsiva non è nella posizione di coda
- Il metodo potrebbe essere sovrascritto
- Il metodo non è finale (caso speciale del precedente)
Si trova poco prima dello def
in una definizione di metodo. Funziona nella REPL.
Qui importiamo l'annotazione e proviamo a contrassegnare un metodo come @tailrec
.
scala> import annotation.tailrec
import annotation.tailrec
scala> @tailrec def length(as: List[_]): Int = as match {
| case Nil => 0
| case head :: tail => 1 + length(tail)
| }
<console>:7: error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position
@tailrec def length(as: List[_]): Int = as match {
^
Oops!L'ultima chiamata è 1.+()
, non length()
! Cerchiamo di riformulare il metodo:
scala> def length(as: List[_]): Int = {
| @tailrec def length0(as: List[_], tally: Int = 0): Int = as match {
| case Nil => tally
| case head :: tail => length0(tail, tally + 1)
| }
| length0(as)
| }
length: (as: List[_])Int
noti che length0
è automaticamente privata perché è definito nell'ambito di un altro metodo.
Espandendo ciò che hai detto sopra, Scala può ottimizzare solo le chiamate tail per un singolo metodo. Le chiamate reciprocamente ricorsive non saranno ottimizzate. –
Detesto essere uno schizzinoso, ma nel tuo esempio nel caso Nil dovresti tornare a contare per una corretta funzione di lunghezza della lista altrimenti otterrai sempre 0 come valore di ritorno quando la ricorsione finisce. –
- 1. Erlang: stackoverflow con funzione ricorsiva non ottimizzata per la coda?
- 2. Posso creare un'espressione ricorsiva ottimizzata chiamata coda?
- 3. F # Coda Funzione ricorsiva Esempio
- 4. Compilazione C# con ottimizzazione ricorsiva della coda?
- 5. Come posso garantire che uno stato reactjs sia aggiornato e quindi chiamare una funzione?
- 6. La seguente funzione è ricorsiva in coda?
- 7. Come scrivere una funzione ricorsiva in coda senza perdite utilizzando Stream.cons in Scala?
- 8. Come posso garantire che il comportamento illegale non sia eseguibile?
- 9. Funzione ricorsiva che chiama in JavaScript
- 10. Come garantire che il metodo toString() sia reimplementato in classe?
- 11. Scala/C++: funzione ricorsiva di coda invece del ciclo di input
- 12. progettare una coda che supporta la funzione getMedian
- 13. Utilizzare ** kwargs sia nella chiamata che nella definizione della funzione
- 14. Come farei per rendere questa coda ricorsiva?
- 15. Flusso delimitato dalla coda ricorsiva di coppie di interi (Scala)?
- 16. Qual è il modo migliore per garantire che un argomento Function sia serializzabile?
- 17. javascript ritorno della funzione ricorsiva
- 18. Questa funzione utilizza la ricorsione della coda?
- 19. scala: implementare una generica funzione di max ricorsiva
- 20. Come posso garantire che una stringa Bash sia alfanumerica, senza un carattere di sottolineatura?
- 21. La valutazione della funzione constexpr può essere ottimizzata in caso di ricorsione in coda
- 22. Perché il compilatore Scala non applicherà l'ottimizzazione della coda, a meno che un metodo non sia definitivo?
- 23. Problema della funzione ricorsiva PHP?
- 24. Istanza di funzione poco ricorsiva non a coda
- 25. La mia funzione di foldl riscritta è ottimizzata?
- 26. Agenti Clojure che consumano da una coda
- 27. Utilizzo di SBT per gestire progetti che contengono sia Scala che Python
- 28. Come garantire che l'elenco contenga elementi univoci?
- 29. Funzione ricorsiva che causa un overflow dello stack
- 30. Procedura consigliata per utilizzare la scala immutabile Coda
Suppongo che questo sia un po 'come l'annotazione "override" in Java - il codice funziona senza, ma se lo metti lì ti dice se hai fatto un errore. –