F # Esempio di funzione ricorsiva di coda

Sono nuovo di F # e stavo leggendo sulle funzioni ricorsive della coda e speravo che qualcuno potesse darmi due diverse implementazioni di una funzione foo – una che è ricorsiva della coda e una che non è così che posso capire meglio il principio.

Inizia con un compito semplice, come mappare gli elementi da ‘a a’ b in una lista. Vogliamo scrivere una funzione che ha la firma

val map: ('a -> 'b) -> 'a list -> 'b list 

Dove

 map (fun x -> x * 2) [1;2;3;4;5] == [2;4;6;8;10] 

Inizia con la versione ricorsiva senza coda :

 let rec map f = function | [] -> [] | x::xs -> fx::map f xs 

Questo non è ricorsivo della coda perché la funzione ha ancora del lavoro da fare dopo aver effettuato la chiamata ricorsiva. :: è zucchero sintattico per List.Cons(fx, map f xs) .

La natura non ricorsiva della funzione potrebbe essere un po ‘più ovvia se ho riscritto l’ultima riga come | x::xs -> let temp = map f xs; fx::temp | x::xs -> let temp = map f xs; fx::temp | x::xs -> let temp = map f xs; fx::temp – ovviamente sta lavorando dopo la chiamata ricorsiva.

Usa una variabile accumulatore per renderla ricorsiva in coda:

 let map fl = let rec loop acc = function | [] -> List.rev acc | x::xs -> loop (fx::acc) xs loop [] l 

Ecco che stiamo costruendo una nuova lista in una variabile acc . Poiché la lista si accumula al contrario, dobbiamo invertire la lista di output prima di restituirla all’utente.

Se ti preoccupi di una piccola distorsione della mente, puoi usare il passaggio di continuazione per scrivere il codice in modo più sintetico:

 let map fl = let rec loop cont = function | [] -> cont [] | x::xs -> loop ( fun acc -> cont (fx::acc) ) xs loop id l 

Poiché la chiamata al loop e al cont sono le ultime funzioni chiamate senza lavoro aggiuntivo, sono ricorsive in coda.

Questo funziona perché la continuazione cont viene catturata da una nuova continuazione, che a sua volta viene catturata da un’altra, risultante in una sorta di struttura dati ad albero come segue:

 (fun acc -> (f 1)::acc) ((fun acc -> (f 2)::acc) ((fun acc -> (f 3)::acc) ((fun acc -> (f 4)::acc) ((fun acc -> (f 5)::acc) (id []))))) 

che crea un elenco in ordine senza che sia necessario annullarlo.


Per quanto vale, inizia a scrivere funzioni in modo ricorsivo non-tail, sono più facili da leggere e lavorare.

Se si dispone di una grande lista, utilizzare una variabile di accumulo.

Se non riesci a trovare un modo per utilizzare un accumulatore in un modo conveniente e non hai altre opzioni a tua disposizione, usa le continuazioni. Personalmente considero l’uso non banale e pesante delle continuazioni difficili da leggere.

Un tentativo di spiegazione più breve rispetto agli altri esempi:

 let rec foo n = match n with | 0 -> 0 | _ -> 2 + foo (n-1) let rec bar acc n = match n with | 0 -> acc | _ -> bar (acc+2) (n-1) 

foo non è ricorsivo in coda, perché foo deve chiamare ricorsivamente in modo da poter valutare “2 + foo (n-1)” e restituirlo.

la barra è ricorsiva della coda, poiché la barra non deve utilizzare il valore restituito della chiamata ricorsiva per restituire un valore. Può semplicemente lasciare che la barra ricorsivamente chiamata restituisca immediatamente il suo valore (senza risalire fino allo stack chiamante). Il compilatore vede questo e ‘imbroglia’ riscrivendo la ricorsione in un ciclo.

Cambiare l’ultima riga nella barra su “| _ -> 2+ (bar (acc + 2) (n-1))” distruggerebbe la ricorsione della coda.

Ecco un esempio più ovvio, confrontalo con ciò che faresti normalmente per un fattoriale.

 let factorial n = let rec fact n acc = match n with | 0 -> acc | _ -> fact (n-1) (acc*n) fact n 1 

Questo è un po ‘complesso, ma l’idea è di avere un accumulatore che mantenga un conto corrente piuttosto che modificare il valore di ritorno.

Inoltre, questo stile di wrapping di solito è una buona idea, in questo modo il chiamante non deve preoccuparsi di inserire l’accumulatore (nota che il fatto è locale per la funzione)

Sto imparando anche F #. Le seguenti sono ricorsive non tail e funzione ricorsiva della coda per calcolare i numeri dei fibonacci.

Versione ricorsiva non a coda

 let rec fib = function | n when n < 2 -> 1 | n -> fib(n-1) + fib(n-2);; 

Versione ricorsiva di coda

 let fib n = let rec tfib n1 n2 = function | 0 -> n1 | n -> tfib n2 (n2 + n1) (n - 1) tfib 0 1 n;; 

Nota: poiché il numero di fibanacci potrebbe crescere molto velocemente, è ansible sostituire l’ultima riga tfib 0 1 n
tfib 0I 1I n per trarre vantaggio da Numerics.BigInteger Structure in F #

Inoltre, durante i test, non dimenticare che la ricorsione su coda indiretta (tailcall) è distriggersta per impostazione predefinita durante la compilazione in modalità Debug. Ciò può causare la ricorsione del tailcall per sovraccaricare lo stack in modalità Debug ma non in modalità Release.