Come faccio a sapere se una funzione è ricorsiva alla coda in F #

Question

Ho scritto la seguente funzione:

let str2lst str =
    let rec f s acc =
      match s with
        | "" -> acc
        | _  -> f (s.Substring 1) (s.[0]::acc)
    f str []

Come posso sapere se il compilatore F # lo ha trasformato in un ciclo? C'è un modo per scoprirlo senza usare Reflector (non ho esperienza con Reflector e non conosco C #)?

Modifica: Inoltre, è possibile scrivere una funzione ricorsiva di coda senza usare una funzione interna, oppure è necessario che il loop risieda?

Inoltre, esiste una funzione in F # std lib per eseguire una determinata funzione un numero di volte, ogni volta assegnandole l'ultimo output come input? Diciamo che ho una stringa, voglio eseguire una funzione sulla stringa, quindi eseguirla di nuovo sulla stringa risultante e così via ...

Answer 1

Purtroppo non esiste un modo banale.

Non è troppo difficile leggere il codice sorgente e usare i tipi e determinare se qualcosa è una chiamata di coda mediante ispezione (è "l'ultima cosa" e non in un blocco "prova"), ma le persone secondo- indovina e fa errori. Non esiste un modo automatizzato semplice (diverso dall'ispezione del codice generato).

Ovviamente, puoi semplicemente provare la tua funzione su un grosso pezzo di dati di test e vedere se esplode o meno.

Il compilatore F # genererà istruzioni .tail IL per tutte le chiamate di coda (a meno che non vengano utilizzate le flag del compilatore per spegnerle - utilizzate per quando si desidera mantenere i frame dello stack per il debug), ad eccezione delle funzioni ricorsive della coda direttamente sarà ottimizzato in loop. (EDIT: penso che oggigiorno anche il compilatore F # non riesca a emettere .tail nei casi in cui può provare che non ci sono loop ricorsivi attraverso questo sito di chiamata; questa è un'ottimizzazione dato che il codice operativo .tail è un po 'più lento su molte piattaforme.)

'tailcall' è una parola chiave riservata, con l'idea che una futura versione di F # potrebbe permetterti di scrivere ad es.

tailcall func args

e quindi ricevi un avviso / errore se non è una chiamata di coda.

Solo le funzioni che non sono naturalmente ricorsive alla coda (e quindi necessitano di un parametro di accumulatore aggiuntivo) ti "forzeranno" nel linguaggio della "funzione interna".

Ecco un esempio di codice di ciò che hai chiesto:

let rec nTimes n f x =
    if n = 0 then
        x
    else
        nTimes (n-1) f (f x)

let r = nTimes 3 (fun s -> s ^ " is a rose") "A rose"
printfn "%s" r

Answer 2

Mi piace la regola empirica formulata da Paul Graham in Su Lisp : se rimane lavoro da fare , ad es. manipolando l'output della chiamata ricorsiva, quindi la chiamata non è ricorsiva della coda.