hàm đệ quy đuôi để tìm chiều sâu của một cái cây trong Ocaml

Question

Tôi có một loại tree quy định như sau

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

Tôi có một chức năng để tìm ra độ sâu của cây như sau

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

này chức năng không phải là đệ quy đuôi. Có cách nào để tôi viết hàm này theo cách đệ quy đuôi không?

Answer 1

Bạn có thể thực hiện điều này bằng cách chuyển chức năng này thành CPS (Kiểu chuyển tiếp tục). Ý tưởng là thay vì gọi số depth left và sau đó tính toán mọi thứ dựa trên kết quả này, bạn gọi số depth left (fun dleft -> ...), trong đó đối số thứ hai là "cần tính toán gì sau khi kết quả (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) 

Đây là mẹo nổi tiếng có thể làm cho bất kỳ hàm nào đệ quy đuôi. Voilà, đó là đuôi-rec.

Bí quyết nổi tiếng tiếp theo trong túi là "hủy kết nối" kết quả CPS. Việc biểu diễn các phần tiếp theo (các phần (fun dleft -> ...)) như các chức năng gọn gàng, nhưng bạn có thể muốn xem nó trông như dữ liệu. Vì vậy, chúng tôi thay thế từng đóng này bằng một hàm tạo cụ thể của một kiểu dữ liệu, để nắm bắt các biến miễn phí được sử dụng trong nó.

Ở đây chúng tôi có ba đóng cửa tiếp tục: (fun dleft -> depth right (fun dright -> k ...)), mà chỉ tái sử dụng các biến môi trường right và k, (fun dright -> ...), mà reuses k và bây giờ có sẵn trái kết quả dleft, và (fun d -> d), việc tính toán ban đầu, điều đó không nắm bắt được bất cứ điều gì .

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

Chức năng defunctorized trông như thế này:

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

Thay vì xây dựng một hàm k và áp dụng nó trên lá (k 0), tôi xây dựng một dữ liệu kiểu ('a, int) cont, mà cần phải được sau eval được ưu tiên tính toán kết quả. eval, khi nó được thông qua một Kleft, những gì đóng cửa (fun dleft -> ...) đã làm, đó là nó đệ quy gọi depth trên cây con phải. eval và depth là đệ quy lẫn nhau.

Bây giờ, hãy nhìn vào số ('a, 'b) cont, kiểu dữ liệu này là gì? Đó là một danh sách!

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

Và danh sách là ngăn xếp. Những gì chúng ta có ở đây thực sự là một sự cải tiến (chuyển đổi thành dữ liệu) của ngăn xếp cuộc gọi của hàm đệ quy trước đó, với hai trường hợp khác nhau tương ứng với hai kiểu gọi không khác nhau.

Lưu ý rằng việc khử chức năng chỉ ở đó để giải trí. Trong pratice phiên bản CPS là ngắn, dễ dàng để lấy được bằng tay, khá dễ đọc, và tôi sẽ khuyên bạn nên sử dụng nó. Các đóng cửa phải được cấp phát trong bộ nhớ, nhưng các thành phần của ('a, 'b) cont - mặc dù chúng có thể được biểu diễn gọn gàng hơn. Tôi sẽ dính vào phiên bản CPS trừ khi có những lý do rất tốt để làm điều gì đó phức tạp hơn.

Answer 2

Trong trường hợp này (chiều sâu tính toán), bạn có thể tích lũy qua cặp (subtree depth * subtree content) để có được những đuôi-đệ quy hàm sau:

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

Đối với trường hợp tổng quát hơn, bạn thực sự sẽ cần phải sử dụng Chuyển đổi CPS được mô tả bởi Gabriel.

Answer 3

Có một giải pháp gọn gàng và generic sử dụng fold_tree và CPS - liên tục qua phong cách:

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