F # Coda Funzione ricorsiva Esempio

Question

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.

Answer 1

Iniziare con un'attività semplice, come associare elementi da 'a a' b in un elenco. 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 non-coda ricorsiva versione:

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

Questo non è ricorsiva di coda perché la funzione ha ancora del lavoro da fare dopo aver effettuato la chiamata ricorsiva. :: è zucchero sintattico per List.Cons(f x, 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; f x::temp - ovviamente sta funzionando dopo la chiamata ricorsiva.

Utilizzare un accumulatore variabile per renderlo ricorsiva coda:

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

Ecco stiamo costruendo un nuovo elenco in una variabile acc. Poiché la lista si accumula al contrario, dobbiamo invertire la lista di output prima di restituirla all'utente.

Se siete dentro per un po 'ordito mente, è possibile utilizzare continuazione passando di scrivere il codice più succintamente:

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

Dal momento che la chiamata a loop e cont sono le ultime funzioni chiamate senza lavoro aggiuntivo, sono ricorsivi in ​​coda.

Ciò funziona perché il proseguimento cont viene catturata da una nuova continuazione, che a sua volta è catturato da un altro, causando una sorta di albero come la struttura dati 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 costruisce un elenco in ordine senza che sia necessario invertire la procedura.

Per quello che vale, iniziare a scrivere funzioni in modo ricorsivo senza coda, sono più facili da leggere e lavorare.

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

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.

Answer 2

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 è coda ricorsiva, perché foo deve chiamare foo ricorsivo per valutare "2 + foo (n-1)" e restituirlo.

bar è ricorsivo in 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.

Answer 3

Inoltre, durante il test, non dimenticare che la ricorsione a coda indiretta (tailcall) è disattivata 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.

Answer 4

Ecco un esempio più ovvio, confrontarlo con ciò che si farebbe 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 'complessa, ma l'idea è che si dispone di un accumulatore che mantiene un riscontro corrente, piuttosto che modificare il valore di ritorno.

Inoltre, questo stile di avvolgimento di solito è una buona idea, in questo modo il chiamante non ha bisogno di preoccuparsi di semina l'accumulatore (si noti che fatto è locale alla funzione)

Answer 5

sto imparando F # troppo . Quelli che seguono sono ricorsive non tail e funzione ricorsiva della coda per calcolare i numeri dei fibonacci.

non-coda versione ricorsiva

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

Tail versione ricorsiva

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

Nota: dal momento che il numero di fibanacci potrebbe crescere veramente veloce si potrebbe sostituire ultima riga tfib 0 1 n-
tfib 0I 1I n sfruttare la struttura Numerics.BigInteger in F #