使用二叉樹型

Question

我有這種類型的聲明，表示二叉樹：

data Bst a = Empty | Node (Bst a) a (Bst a) 

由於我是新來的Haskell，我想不出如何使用它。你能告訴我如何初始化它的一些實例嗎？

Answer 1

您的數據聲明指出有兩種方法構建Bst：使用Empty構造函數或使用Node構造函數。

-- An empty Bst 
bst1 = Empty 

-- A Bst containing a single value. 
bst2 = Node Empty 42 Empty 

-- A Bst containing 3 values, 2 at the root, 1 in the left child and 3 in the right child. 
bst3 = Node (Node Empty 1 Empty) 2 (Node Empty 3 Empty) 

Answer 2

單個int節點：

2 

Node Empty (2::Int) Empty 

樹：

2 
/\ 
    1 3 

Node (Node Empty 1 Empty) 2 (Node Empty 3 Empty) :: Bst Int 


    2 
/\ 
    1 3 
     \ 
     5 

Node (Node Empty 1 Empty) 2 (Node Empty 3 (Node Empty 5 Empty)) :: Bst Int 

Answer 3

我會稍微重寫你的宣言，使用的參數的更地道爲了Node：

data Bst a = Empty | Node a (Bst a) (Bst a) 

Empty和Node是什麼哈斯克爾調用構造。構造函數可以使用兩種方式：

1. 作爲構造它們類型值的函數;
2. 如在特殊模式匹配的語法模式來分析和他們的類型的拆解值。

如果我們加載類型爲ghci解釋，我們可以使用ghci中的:t命令顯示類型的構造函數：

Ok, modules loaded: Main. 
*Main> :t Empty 
Empty :: Bst a 
*Main> :t Node 
Node :: a -> Bst a -> Bst a -> Bst a 
*Main> 

所以Empty是對任何a鍵入Bst a恆定的，而Node是產生Bst a三個參數的函數：一個a和兩個Bst a。因此，要構建類型的值，可以使用一個構造函數，給它所需數量的參數（沒有在Empty的情況下，三爲Node），以及正確的類型。

讓我再次強調這一點：您可以使用構造函數，就像您可以使用與構造函數相同類型的任何表達式一樣。因此，舉例來說，就像你可以部分在Haskell應用功能（它比它需要應用到更少的參數），可以部分地應用構造：Node "foo" Empty具有類型Bst String -> Bst String。