OCaml: Các chức năng của cây

Question

Có bất kỳ mô-đun hoặc chức năng nào để xử lý cây không? Tôi có một loại trông như thế này:

type t = 
     Leaf of string (* todo: replace with 'a *) 
     | Node of string * t list 

và tôi đang đấu tranh để làm chèn, loại bỏ các subtrees vv

Tôi đã sử dụng googles nhưng không thể tìm thấy bất cứ điều gì.

Answer 1

Đọc phần cài đặt mô-đun Đặt trong nguồn của thư viện chuẩn OCaml. Chúng được thực hiện với cây nhị phân, chỉ phức tạp hơn một chút so với của bạn.

(Tôi muốn giới thiệu bạn bắt đầu với cây nhị phân thay vì có một danh sách các trẻ em như bạn dường như đã được định nghĩa)

Answer 2

Trên thực tế nó phụ thuộc vào cách bạn muốn cây của bạn để làm việc, ví dụ nếu có trật tự giữa các yếu tố và như vậy.

Nếu không, bạn có thể sử dụng các thuật toán đã biết trên cây, nếu bạn có ý tưởng về nó bằng các ngôn ngữ khác C hoặc Java chẳng hạn, tôi có thể dịch nó sang OCAML.

Answer 3

Trong quá khứ, tôi đã sử dụng ocamlgraph. Đây không phải là một lib tầm thường để sử dụng, nhưng nếu bạn cần phải chèn các nút và thay đổi đường dẫn, đó có thể là lừa, tôi đã không bao giờ được sử dụng trong một bối cảnh cây ... mặc dù ...

Và trích xuất từ tài liệu ngôn ngữ:

Cách sử dụng phổ biến nhất của các loại biến thể là để mô tả dữ liệu đệ quy cấu trúc. Hãy xem xét ví dụ loại cây nhị phân:

#type 'a btree = Empty | Node of 'a * 'a btree * 'a btree;; 
type 'a btree = Empty | Node of 'a * 'a btree * 'a btree 

Định nghĩa này lần đọc như sau: một cây nhị phân chứa giá trị của loại 'một (một loại tùy ý) là một trong hai trống rỗng, hoặc là một nút có chứa một giá trị loại 'a và hai subtrees cũng chứa các giá trị thuộc loại' a, có nghĩa là, hai 'một btree.

Thao tác trên cây nhị phân là được biểu diễn tự nhiên dưới dạng đệ quy các chức năng theo cùng cấu trúc làm định nghĩa loại chính nó. Đối với dụ, đây là chức năng thực hiện tra cứu và chèn trong cây nhị phân ra lệnh (yếu tố tăng từ trái sang phải):

#let rec member x btree = 
    match btree with 
    Empty -> false 
    | Node(y, left, right) -> 
     if x = y then true else 
     if x < y then member x left else member x right;; 
val member : 'a -> 'a btree -> bool = <fun> 

#let rec insert x btree = 
    match btree with 
    Empty -> Node(x, Empty, Empty) 
    | Node(y, left, right) -> 
     if x <= y then Node(y, insert x left, right) 
       else Node(y, left, insert x right);; 
val insert : 'a -> 'a btree -> 'a btree = <fun> 

Hope this helps

Answer 4

Có một datatype Ptree Matt McDonnell làm những gì bạn cần, tôi nghĩ vậy.