Tail funzione ricorsiva per trovare la profondità di un albero in OCaml

Question

Ho un tipo tree definito come segue

type 'a tree = Leaf of 'a | Node of 'a * 'a tree * 'a tree ;; 

Ho una funzione per trovare la profondità dell'albero come segue

let rec depth = function 
    | Leaf x -> 0 
    | Node(_,left,right) -> 1 + (max (depth left) (depth right)) 
;; 

Questo la funzione non è ricorsiva della coda. C'è un modo per me di scrivere questa funzione in modo ricorsivo in coda?

Answer 1

È possibile farlo banalmente trasformando la funzione in CPS (Continuing Passing Style). L'idea è che invece di chiamare depth left e quindi calcolare le cose in base a questo risultato, si chiami depth left (fun dleft -> ...), dove il secondo argomento è "cosa calcolare quando il risultato (dleft) è disponibile".

let depth tree = 
    let rec depth tree k = match tree with 
    | Leaf x -> k 0 
    | Node(_,left,right) -> 
     depth left (fun dleft -> 
     depth right (fun dright -> 
      k (1 + (max dleft dright)))) 
    in depth tree (fun d -> d) 

Questo è un trucco ben noto che può fare qualsiasi funzione ricorsiva in coda. Voilà, è coda-rec.

Il prossimo trucco ben noto nella borsa è quello di "defunzionalizzare" il risultato del CPS. La rappresentazione delle continuazioni (le parti (fun dleft -> ...)) come funzioni è ordinata, ma potresti voler vedere come sono i dati. Quindi sostituiamo ciascuna di queste chiusure con un costruttore concreto di un tipo di dati, che cattura le variabili libere utilizzate in esso.

Qui abbiamo tre chiusure continuazione: (fun dleft -> depth right (fun dright -> k ...)), che riutilizza solo le variabili di ambiente e rightk, (fun dright -> ...), che riutilizza k e l'ormai disponibili sinistra risultato dleft, e (fun d -> d), il calcolo iniziale, che non catturare qualsiasi cosa .

type ('a, 'b) cont = 
    | Kleft of 'a tree * ('a, 'b) cont (* right and k *) 
    | Kright of 'b * ('a, 'b) cont  (* dleft and k *) 
    | Kid 

La funzione defunctorized assomiglia a questo:

let depth tree = 
    let rec depth tree k = match tree with 
    | Leaf x -> eval k 0 
    | Node(_,left,right) -> 
     depth left (Kleft(right, k)) 
    and eval k d = match k with 
    | Kleft(right, k) -> 
     depth right (Kright(d, k)) 
    | Kright(dleft, k) -> 
     eval k (1 + max d dleft) 
    | Kid -> d 
    in depth tree Kid 
;; 

Invece di costruire una funzione k e la sua applicazione sulle foglie (k 0), costruisco un dato di tipo ('a, int) cont, che deve essere in seguito eval per calcolare un risultato. eval, quando viene passato uno Kleft, fa ciò che stava facendo la chiusura (fun dleft -> ...), cioè chiama ricorsivamente depth nella sottostruttura di destra. eval e depth sono reciprocamente ricorsivi.

Ora guarda attentamente ('a, 'b) cont, che cos'è questo tipo di dati? È una lista!

type ('a, 'b) next_item = 
    | Kleft of 'a tree 
    | Kright of 'b 

type ('a, 'b) cont = ('a, 'b) next_item list 

let depth tree = 
    let rec depth tree k = match tree with 
    | Leaf x -> eval k 0 
    | Node(_,left,right) -> 
     depth left (Kleft(right) :: k) 
    and eval k d = match k with 
    | Kleft(right) :: k -> 
     depth right (Kright(d) :: k) 
    | Kright(dleft) :: k -> 
     eval k (1 + max d dleft) 
    | [] -> d 
    in depth tree [] 
;; 

E una lista è una pila. Quello che abbiamo qui è in realtà una reificazione (trasformazione in dati) dello stack di chiamate della funzione ricorsiva precedente, con due casi diversi corrispondenti ai due diversi tipi di chiamate non-tailrec.

Si noti che la defunzionalizzazione è solo lì per divertimento. In pratica la versione di CPS è breve, facile da ottenere a mano, piuttosto facile da leggere, e io consiglierei di usarla. Le chiusure devono essere allocate in memoria, ma lo sono anche gli elementi di ('a, 'b) cont - anche se potrebbero essere rappresentati in modo più compatto ». Vorrei attenermi alla versione CPS a meno che non ci siano ottimi motivi per fare qualcosa di più complicato.

Answer 2

In questo caso (profondità di calcolo), è possibile accumulare mediante coppie (subtree depth * subtree content) avere la seguente funzione ricorsiva in coda:

let depth tree = 
    let rec aux depth = function 
    | [] -> depth 
    | (d, Leaf _) :: t -> aux (max d depth) t 
    | (d, Node (_,left,right)) :: t -> 
     let accu = (d+1, left) :: (d+1, right) :: t in 
     aux depth accu in 
aux 0 [(0, tree)] 

Per i casi più generali, è infatti necessario utilizzare il Trasformazione CPS descritta da Gabriel.

Answer 3

C'è una soluzione ordinata e generico utilizzando fold_tree e CPS - passaggio continuo stile:

let fold_tree tree f acc = 
    let loop t cont = 
    match tree with 
    | Leaf -> cont acc 
    | Node (x, left, right) -> 
     loop left (fun lacc -> 
     loop right (fun racc -> 
      cont @@ f x lacc racc)) 
    in loop tree (fun x -> x) 

let depth tree = fold_tree tree (fun x dl dr -> 1 + (max dl dr)) 0