fold_tree trong OCaml

Question

Như Bạn có thể biết, có chức năng bậc cao trong OCaml, chẳng hạn như fold_left, fold_right, lọc, vv

Mở khóa học của tôi trong lập trình chức năng đã được giới thiệu hàm có tên fold_tree, mà là một cái gì đó giống như fold_left/phải, không phải trên danh sách, nhưng trên cây (nhị phân). Nó trông giống như thế này:

let rec fold_tree f a t = 
    match t with 
    Leaf -> a | 
    Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);; 

đâu cây được định nghĩa là:

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

OK, đây là câu hỏi của tôi: làm thế nào để làm công việc chức năng fold_tree? Bạn có thể cho tôi một số ví dụ và giải thích bằng ngôn ngữ của con người không?

Answer 1

Đây là đề xuất kiểu, đặt các thanh ở đầu dòng. Nó làm cho nó rõ ràng hơn khi một vụ án bắt đầu. Để nhất quán, thanh đầu tiên là tùy chọn nhưng được khuyên dùng.

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

let rec fold_tree f a t = 
    match t with 
     | Leaf -> a 
     | Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);; 

---

Đối với cách thức hoạt động, xem xét các cây sau:

let t = Node(Leaf, 5, Node(Leaf, 2, Leaf));; 

Với kiểu int tree.

Nhìn bề ngoài, t trông như thế này:

 
    5 
/\ 
() 2 
    /\ 
    ()() 

Và gọi fold_tree, chúng tôi cần một chức năng để kết hợp các giá trị. Dựa trên cách sử dụng trong trường hợp Node, f lấy 3 đối số, tất cả cùng loại của cây và trả về giống nhau. Chúng tôi sẽ làm điều này:

let f x l r = x + l + r;; (* add all together *) 
fold_tree f 1 t;; 

Nó sẽ giúp hiểu điều gì xảy ra trong từng trường hợp.Đối với bất kỳ số Leaf nào, số tiền được trả lại. Đối với bất kỳ Node, nó kết hợp giá trị được lưu trữ và kết quả của gấp các subtrees trái và phải. Trong trường hợp này, chúng tôi chỉ thêm các số mà mỗi chiếc lá được tính là một. Kết quả trên gấp cây này là 10.

Answer 2

Dường như f là một chức năng giảm ba tham số, a là yếu tố trung tính giảm của chúng tôi, và t là gốc rễ, vì vậy:

cho một nhị phân như (tôi không nhớ rất tốt cú pháp các loại biến thể, vì vậy xin vui lòng được condescendent đây)

let r = Node(Node(Node(Leaf,3,Leaf),2,Node(Leaf,4,Leaf)),1,Node(Node(Leaf,6,Leaf),5,Node(Leaf,7,Leaf))) 

nếu bạn muốn tổng hợp tất cả các nút, các chức năng sẽ được gọi như:

let add x y z = x + y + z 
fold_tree add 0 r 

và chúng tôi sẽ nhận được t xuất hiện như một nút, vì vậy chúng ta có:

(add 1 (fold_tree add 0 Node(Node(Leaf,3,Leaf),2,Node(Leaf,4,Leaf))) (fold_tree add 0 Node(Node(Leaf,6,Leaf),5,Node(Leaf,7,Leaf)))) 

nếu chúng ta mở rộng nó hơn một chút, chúng tôi nhận được:

(add 1 (add 2 (fold_tree add 0 Node(Leaf,3,Leaf)) (fold_tree add 0 Node(Leaf,4,Leaf))) (add 5 (fold_tree add 0 Node(Leaf,6,Leaf)) (fold_tree add 0 Node(Leaf,7,Leaf)))) 

và một lần nữa, chúng ta đang phù hợp với lá:

(add 1 (add 2 (add 3 0 0) (add 4 0 0)) (add 5 (add 6 0 0) (add 7 0 0)) 
(add 1 (add 2 3 4) (add 5 6 7)) 
(add 1 9 18) 

để cuối cùng nhận được:

28 

Hy vọng điều đó sẽ hữu ích.

Answer 3

Đây là một cách để suy nghĩ về fold_right trên danh sách: một danh sách là ví dụ

(1 :: (2 :: (3 :: []))) 

và bạn tái giải thích danh sách với một hoạt động nhị phân mới ở vị trí của :: (và một hằng số mới thay của []).

fold_right (+) l 0 = (1 + (2 + (3 + 0))) 

Nếu bạn muốn hoàn toàn không có gì trong danh sách, bạn có thể chuyển hàm cons làm hàm và danh sách trống làm phần tử trung tính. Vì vậy, theo nghĩa nào đó, fold_right rất chung chung: thậm chí nó còn cho phép bạn không mất bất kỳ thông tin nào.

fold_tree trong câu hỏi của bạn là ý tưởng tương tự cho kiểu dữ liệu của cây. Nếu bạn muốn diễn giải lại cây của mình, bạn chuyển nó thành một hàm mới cho các nút sẽ được áp dụng thay vì hàm tạo (constructor) Node. Nếu bạn muốn có một cây giống hệt nhau, bạn có thể áp dụng nó với Leaf là trung tính và (fun x l r -> Node (l, x, r)) làm chức năng. Tương tự như fold_left cho danh sách, ứng dụng ví dụ này không phải là rất thú vị, nhưng nó có nghĩa là fold_left là một biến đổi rất chung chung (thuật ngữ kỹ thuật là morphism).

Bạn cũng có thể tổng hợp các phần tử của cây với hàm (fun x l r -> x + l + r) chẳng hạn.

Answer 4

Hãy lấy một cây mẫu.

let t = Node (Node (Leaf, 10, Leaf), 1, Node (Node (Leaf, 20, Leaf), 11, Leaf)) 

Định nghĩa chung về hoạt động fold là bạn thay thế hàm tạo theo hàm, ở mọi nơi trong cây.

general_fold_tree node leaf t = 
    node (node leaf 10 leaf) 1 (node (node leaf 20 leaf) 11 leaf) 

node là một hàm xây dựng một một cái gì đó từ một trái một cái gì đó, một yếu tố và quyền một cái gì đó, giống như Node là một nhà xây dựng mà xây dựng một cây từ một cây con bên trái, một nút nội dung và một cây con phải. leaf là hằng số, khớp với hàm tạo liên tục Leaf.

let rec general_fold_tree (node : 'b -> 'a -> 'b -> 'b) (leaf : 'a) (t : 'a tree) : 'b = 
    let recurse t = general_fold_tree node leaf t in 
    match t with 
    | Node (l, x, r) -> node (recurse l) x (recurse r) 
    | Leaf -> leaf 

Chú ý rằng các loại chức năng phù hợp với các định nghĩa loại, ngoại trừ nơi định nghĩa kiểu mô tả việc xây dựng một 'a tree, hàm lần mô tả việc xây dựng bất kỳ 'b.

Các thao tác trông giống như nếp gấp chung vẫn được gọi là gấp. Ví dụ, trên danh sách, List.fold_right là tổng quát theo định nghĩa trên; List.fold_left là một biến thể áp dụng chức năng theo cách khác vòng (fold_left tương đương với đảo ngược + fold_right + ngược lại, mặc dù nó rõ ràng hơn và hiệu quả hơn).

của bạn riêng fold_tree là một biến thể đơn giản gấp chung này, nơi các chức năng nút có đối số của nó theo một thứ tự khác nhau từ các nhà xây dựng:

let equrts_fold_tree f a t = 
    let node l x r = f x l r in 
    general_fold_tree node a t 

Answer 5

Bạn có thể thưởng thức đọc

http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/

http://lorgonblog.wordpress.com/2008/04/09/catamorphisms-part-three/

trong F #, nhưng F # rất giống đến OCaml.