Trees trong Haskell

Question

Tuy nhiên việc học Haskell, và tôi có thể không thực sự thấy sự khác biệt giữa

data Tree a = Leaf a | Branch [Tree a] 

và

data Tree a = Leaf a | Branch (Tree a) (Tree a) 

gì là theo tốt nhất cho bạn? Ý nghĩa của hai cách viết này là gì?

Answer 1

Nhánh của nhánh đầu tiên chứa danh sách Cây, vì vậy có thể có bất kỳ số lượng subtrees nào. Thứ hai rõ ràng là hai subtrees, do đó một cây nhị phân.

Answer 2

Trước đây xác định một cây nơi mỗi chi nhánh có thể có nhiều subtrees tùy ý (được biểu thị dưới dạng danh sách cây) và sau đó xác định cây nơi mỗi chi nhánh có chính xác hai subtrees.

Nói cách khác, trước đây là cây chung và cây thứ hai là cây nhị phân.

Vì vậy, cái nào để chọn tùy thuộc vào việc bạn muốn tạo mô hình cây chung hay cây nhị phân.

Answer 3

Tôi đã đặt này như một câu trả lời chứ không phải bình luận để nó có một số định dạng:

data Rose a = Branch a [Rose a] 
    deriving (Show) 


sample1 :: Rose Int 
sample1 = Branch 1 [Branch 2 [], Branch 3 [Branch 5 []], Branch 4 []] 

Đây là giống như các mô-đun Data.Tree thư viện, mặc dù Data.Tree sử dụng lĩnh vực nhãn và một nhập từ đồng nghĩa.

Tôi đã nhìn thấy cả cây này và định nghĩa đầu tiên của bạn được gọi là "Cây hoa hồng" mặc dù chúng có hình dạng hơi khác nhau nên thuật ngữ dường như không hoàn toàn chính xác. Cách giải thích của tôi là danh sách "[Rose a]" được nhúng vào trong một hàm tạo đệ quy đơn nhất định nghĩa nó là một cây Rose.