Tạo các loại đệ quy đa hình trong Haskell

Question

Tôi đang cố tạo loại Cây trong Haskell. Tôi đã sử dụng hàm tạo dữ liệu đơn giản này để lưu trữ một cây trong đó mỗi nút có thể rỗng, là một lá chứa một số nguyên, hoặc là một nút chứa một số nguyên có các nhánh với hai lá/nút khác. Dưới đây là những gì tôi đã có:

module Tree (Tree(Empty, Leaf, Node)) where 

data Tree = Empty 
| Leaf Int 
| Node Tree Int Tree 
deriving(Eq, Ord, Show, Read) 

Điều đó làm việc tốt, nhưng tôi cần phải làm cho loại cây đa hình. Tôi đã thử thay thế 'Int' bằng 'a' nhưng nó có vẻ không hoạt động. Có một hệ thống khác để làm cho các loại đa hình này không?

Answer 1

Thật vậy, bạn có thể cho tham số kiểu cây, như trong ví dụ Alexander Poluektov. Đủ đơn giản! Nhưng tại sao lại dừng ở đó? Chúng ta có thể vui hơn một chút. Thay vì chỉ là một cấu trúc đệ quy với dữ liệu đa hình, bạn có thể làm cho cấu trúc đa hình trong đệ quy chính nó!

Đầu tiên, trừu tượng hóa tham chiếu của cây thành chính nó, theo cùng cách trừu tượng hóa tham chiếu đến Int, thay thế tham chiếu đệ quy bằng thông số mới t. Điều đó khiến chúng tôi có cấu trúc dữ liệu khá mơ hồ này:

data TNode t a = Empty 
       | Leaf a 
       | Node (t a) a (t a) 
       deriving (Eq, Ord, Show, Read) 

Điều này đã được đổi tên thành TNode tại đây vì nó không thực sự là một cây nữa; chỉ là một kiểu dữ liệu đơn giản. Bây giờ, để thu hồi đệ quy gốc và tạo ra một cây, chúng tôi xoay TNode xung quanh và ăn nó với bản thân:

newtype Tree a = Tree (TNode Tree a) deriving (Eq, Ord, Show, Read) 

Bây giờ chúng ta có thể sử dụng Tree này đệ quy, mặc dù buồn bã với chi phí của một số sự nói dài giòng thêm, như vậy:

Tree (Node (Tree Empty) 5 (Tree (Leaf 2))) 

Vì vậy, điều này cung cấp cho chúng tôi, ngoài việc nhập thêm, bạn hỏi? Đơn giản là chúng tôi đã tách cấu trúc cây cơ bản khỏi cả dữ liệu chứa và phương thức mà dữ liệu được xây dựng và xử lý, cho phép chúng tôi viết các hàm chung chung hơn để xử lý một khía cạnh này.

Ví dụ: chúng tôi có thể trang trí cây có thêm dữ liệu hoặc ghép các thứ thừa vào cây mà không ảnh hưởng đến bất kỳ chức năng cây chung nào.Giả sử chúng ta muốn đặt tên cho mỗi phần của cây:

newtype NameTree a = NameTree (String, TNode NameTree a) deriving (Eq, Ord, Show, Read) 

Mặt khác, chúng ta có thể viết chung Logic cây traversal:

toList f t = toList' f (f t) [] 
    where toList' f (Node t1 x t2) xs = toList' f (f t1) (x : toList' f (f t2) xs) 
      toList' f (Leaf x) xs = x:xs 
      toList' _ Empty xs = xs 

Với một hàm để trích xuất các hiện TNode từ một cây đệ quy, chúng tôi có thể sử dụng cây này trên bất kỳ cấu trúc nào như vậy:

treeToList = toList (\(Tree t) -> t) 
nameTreeToList = toList (\(NameTree (_, t)) -> t) 

Tất nhiên, điều này có thể vượt xa những gì bạn đang tìm kiếm, nhưng đó là một hương vị tuyệt vời đa hình và mã chung Haskell cho phép (nay, khuyến khích) một lập trình viên để tạo ra.

Answer 2

data Tree a = Empty 
      | Leaf a 
      | Node (Tree a) a (Tree a) 

Answer 3

Thay thế Int bằng a là khởi đầu đúng, nhưng bạn cũng cần thay thế mỗi lần xuất hiện Tree bằng Tree a (dấu ngoặc đơn khi cần). Phần data Tree cần khai báo rằng Tree có một đối số kiểu được gọi là a. Các Node Tree Int Tree cần phải biểu thị rằng các subtrees là bản thân của loại Tree a và không phải một số loại khác.

Answer 4

Hãy thử đọc một chút về kiểu hàm tạo loại.

Nếu bạn có loại đa hình tùy thuộc vào một số loại biến, thì trình tạo kiểu của bạn phải có loại phản ánh điều đó.

Ví dụ, loại constructor MyBool quy định tại:

data MyBool = False | True 

là loại *. Tức là, hàm tạo kiểu của tôi MyBool không có tham số nào để xác định loại. Nếu tôi viết một cái gì đó như:

data MyMaybe a = Just a | Nothing 

sau đó loại constructor MyMaybe có loại *->*, có nghĩa là, nó cần một "đối số kiểu" để xác định một loại.

Bạn có thể so sánh cách các loại trình tạo kiểu hoạt động với cách thức hoạt động của kiểu hàm tạo dữ liệu.

Trình tạo dữ liệu True có thể là giá trị dữ liệu thuộc loại MyBool trên chính nó, không có tham số nào. Nhưng các nhà xây dựng dữ liệu Just là một giá trị kiểu a -> MyMaybe a, nó sẽ hoạt động hơn một giá trị của loại một để tạo ra một giá trị kiểu MyMaybe a - ví dụ như trong phiên ghci này:

> let x = Just 5 
> :t x 
Maybe Int 
> let y = Just 
> :t y 
a -> Maybe a 

này là nhiều hơn hoặc ít so sánh với sự khác biệt giữa các nhà xây dựng loại MyMaybe và MyBool. Cho rằng MyBool có loại *, bạn có thể có giá trị với loại MyBool, không có bất kỳ tham số loại bổ sung nào. Nhưng MyMaybe không phải là một kiểu riêng của nó - đó là một hàm tạo kiểu mà "hoạt động" trên một kiểu để tạo một kiểu khác, có nghĩa là, kiểu của nó là * -> *. Và như vậy, bạn không thể có những thứ kiểu MyMaybe, nhưng mọi thứ kiểu MyMaybe Int, MyMaybe Bool, MyMaybe [Int], vv ...

Nếu một loại là đa hình, nó cần phải được ít nhất của loại hình * -> *, nhưng nó có thể được *->*->*, như trong:

data MyPair a b = Pair a b 

MyPair cần hai tham số kiểu định nghĩa một kiểu, như trong MyPair Int Bool, MyPair Int Int, vv ...Thông điệp mang về nhà là một cái gì đó giống như: như các nhà xây dựng giá trị có chữ ký kiểu, các nhà thầu kiểu có chữ ký loại, và điều này phải được tính đến khi bạn đang lập kế hoạch một kiểu dữ liệu mới.

http://en.wikipedia.org/wiki/Kind_%28type_theory%29