Mi chiedo se oCaml ottimizzi questo codice come coda ricorsiva e in tal caso F #?Questa funzione utilizza la ricorsione della coda?
let rec sum xs =
match xs with
| [] -> 0
| x :: xs' -> x + sum xs'
Nel caso ricorsivo (vale a dire che xs non è vuoto) l'ultima operazione valutata è l'aggiunta. Affinché la funzione sia ricorsiva in coda, l'ultima operazione valutata deve essere la chiamata ricorsiva alla somma.
Funzioni come questa vengono solitamente definite utilizzando una funzione di supporto con un accumulatore per renderle ricorsive in coda. In questo caso quella sarebbe una funzione che prende la lista da sommare e il valore corrente della somma. Se la lista è vuota, restituirà il valore corrente della somma. Se la lista non è vuota, si chiamerebbe con la coda della lista e il valore corrente della somma + la testa della lista come argomenti. La funzione somma chiamerebbe quindi la funzione helper con la lista e 0 come valore corrente della somma.
No, questo codice non è ricorsivo in coda e ocaml non lo trasformerà. Devi farlo da solo.
Non so per F #, ma dubito che lo ottimizzerà.
Sì, quindi non sembra difficile ottimizzare oCaml. Basta aggiungere un parametro currentVal e chiamare sum xs ', currentSum. Sapendo che è semplice, volevo sapere se ottimizza. Quindi tu dici che non hmm .. Non ho bidoni oCaml su questa macchina, quindi non posso controllare e so perché sarebbe o wouldnt. –
@ acidzombie24 In questo caso potrebbe essere ottimizzato, ma se ci si affida ad esso, si verificheranno degli overflow dello stack in casi leggermente più complicati in cui il compilatore non può effettuare la trasformazione. Ad esempio potresti aspettarti la stessa trasformazione con una funzione pura da un altro modulo, e avresti ragione a pensarci, ma sarebbe impossibile per il compilatore eseguire la trasformazione a causa della compilazione separata e poiché le interfacce non specificano quali funzioni sono puro. –