我正在嘗試在haskell中寫一棵紅黑樹。在紅黑樹的屬性中有一個注釋，所有不包含資料的葉子都是黑色的。
我想寫這樣的東西：
data EmptyNode = EmptyNode{
data = ???,
color = ???, <-- it should black (assume that it is False)
left = ???,
right = ???
}
data NodeBR a = NodeBR {
data :: a,
color :: Bool,
left :: NodeBR,
right :: NodeBR
}
data TreeBR a = EmptyNode | NodeBR a (TreeBR a) (TreeBR a)
我不明白兩件事，什么型別適合我用通常的語言替換 Null（我知道你不能在這里使用未定義）并使用建構式，我如何在 EmptyNode 默認為 False 中指定顏色？
uj5u.com熱心網友回復：
一種解決方案是以更“Haskell”的方式定義紅黑樹（簡稱RBT）。所以有兩種可能的方式來構建 RBT：
Leaf（EmptyNode在您的代碼中）Node a c l r（NodeBR在您的代碼中），a資料在哪里，c顏色在哪里，l也是rRBT。
data RBT a = Leaf | Node a Bool (RBT a) (RBT a)
在上面的行中，我們定義RBT a了具有兩個建構式的資料型別：
Leaf :: RBT aNode :: a -> Bool -> RBT a -> RBT a -> RBT a
意思是：
Leaf是型別RBT aNode是一個函式，取a,Bool(color),RBT a(left tree),RBT a(right tree)，它回傳一個RBT a.
因此，在這種情況下，我們不需要為 指定 NULL Leaf，因為根本不需要這么說（即，對于 Leaf，我們想說沒有資料，沒有左/右子樹）。
要將Leaf其視為黑色，我們可以## Heading ##defineRBT a使用模式匹配的函式：
color :: RBT a -> Bool
color Leaf = False
color (Node _ c _ _) = c
您在代碼中提到的記錄語法color只是生成此類函式的語法糖。但是在這種情況下，使用記錄語法無法為 Leaf 情況生成正確的代碼，因為它們在宣告中并不相同。
因此，當您必須檢查是否存在時RBT a，Leaf您可以只使用模式匹配而不是其他語言中的“if-with-null”。
更新：
正如 amalloy 在評論中提到的，我們可以將顏色定義為單獨的資料型別以提高可讀性：
data Color = Red | Black
data RBT a = Leaf | Node a Color (RBT a) (RBT a)
color :: RBT a -> Color
color Leaf = Black
color (Node _ c _ _) = c
注意Bool和Color是同構的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/528486.html
標籤：哈斯克尔树