Tail funkcja rekurencyjna, aby znaleźć głębokość drzewa w SML

Question

mam typ tree zdefiniowane następująco

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

Mam funkcji, aby odnaleźć głębię drzewie następująco

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

ten funkcja nie jest rekursywna. Czy istnieje sposób, aby napisać tę funkcję w rekursywny sposób ogon?

Answer 1

Można to zrobić w uproszczeniu, zamieniając tę ​​funkcję na CPS (Styl przejścia kontynuacji). Chodzi o to, że zamiast wywoływać depth left, a następnie obliczać rzeczy na podstawie tego wyniku, wywołuje się depth left (fun dleft -> ...), gdzie drugi argument to "co obliczyć, gdy wynik jest dostępny (dleft)".

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) 

Jest to dobrze znana sztuczka, która może pełnić dowolną funkcję rekursywną. Voila, to ogon-rec.

Następną znaną sztuczką w torbie jest "defalizacja" wyniku CPS. Reprezentacja kontynuacji (części (fun dleft -> ...)) jako funkcji jest zadowalająca, ale możesz chcieć zobaczyć, jak to wygląda jako dane. Tak więc zamieniamy każdą z tych zamknięć na konkretny konstruktor typu danych, który przechwytuje wolne zmienne w nim używane.

Tutaj mamy trzy zamknięcia kontynuacji: (fun dleft -> depth right (fun dright -> k ...)), który ponownie wykorzystuje tylko zmienne środowiskowe right i k, (fun dright -> ...), który ponownie wykorzystuje k i teraz-dostępny po lewej wynik dleft i (fun d -> d), początkowy obliczeń, że nic nie uchwycić .

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

Funkcja defunctorized wygląda następująco:

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 
;; 

Zamiast budować funkcję k i wykorzystywanie go na liściach (k 0), zbudować danych typu ('a, int) cont, która musi być później eval aby obliczać wynik. eval, kiedy przechodzi Kleft, robi to, co robiło zamknięcie (fun dleft -> ...), to jest rekurencyjnie wywoływanie depth w prawym poddrzewie. eval i depth są rekursywne.

Teraz spójrz na numer ('a, 'b) cont, jaki jest ten typ danych? To jest 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 [] 
;; 

A lista to stos. To, co mamy tutaj, to w rzeczywistości reifikacja (przekształcenie w dane) stosu wywołań poprzedniej funkcji rekursywnej, z dwoma różnymi przypadkami odpowiadającymi dwóm różnym rodzajom połączeń niezwiązanych z końcem.

Należy pamiętać, że defunctionalization jest dostępny tylko dla zabawy. W praktyce wersja CPS jest krótka, łatwa do wyprowadzenia ręcznie, raczej łatwa do odczytania i polecam jej użycie. Zamknięcia muszą być przydzielone w pamięci, ale tak samo są elementy z ('a, 'b) cont - choć te mogą być reprezentowane w bardziej zwartej formie ". Trzymałbym się wersji CPS, chyba że istnieją bardzo dobre powody, by zrobić coś bardziej skomplikowanego.

Answer 2

W tym przypadku (obliczenie głębokość) może gromadzić się par (subtree depth * subtree content), aby uzyskać następujące ogona funkcji rekurencyjnej:

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)] 

Dla bardziej ogólnych przypadków będzie rzeczywiście trzeba użyć Transformacja CPS opisana przez Gabriela.

Answer 3

Jest schludny i rodzajowe rozwiązanie wykorzystujące fold_tree i CPS - ciągłe styl Podania:

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