我正在Haskell中进行作业，并且对我得到的二进制搜索树的实现有疑问。我用来学习Haskell的书对二进制树使用了以下实现：
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)
这个定义对我来说很有意义，因为它表明一棵树是空树还是包含一个值和两棵树的元素。但是，我在分配中给出的二进制搜索树的实现如下：
data BT a b
= Leaf
| Branch (BT a b) a b (BT a b)
deriving (Eq,Show)
在此实现中，每个分支都代表一对由更多分支或叶子组成的节点吗？还有，与传统方法相比，此方法有哪些优点/缺点？任何帮助将不胜感激！
我认为@chepner已将其钉牢。这旨在成为一个既包含键（类型为a）又包含值（类型为b）的二叉树。
这样想。如果您从定义开始：
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)
，并且想在每个节点上存储键/值对，可以将a类型成对。以下不是合法的Haskell data类型，因为您不能在左侧使用(k,v)，但是它说明了有效类型Tree (k,v)的样子：>
data Tree (k,v) = EmptyTree | Node (k,v) (Tree (k,v)) (Tree (k,v))
通过为类型构造函数k设置v和Tree适当的参数，即用{{1}替换Tree (k,v)，可以使之成为有效的Haskell类型定义。 }：
Tree k v现在，作为一般规则，如果您的数据类型的构造函数包括一对：
data Tree k v = EmptyTree | Node (k,v) (Tree k v) (Tree k v)
或多或少等于：
data SomeType a b = Pair1 (a,b)
毕竟，您可以编写data SomeOtherType a b = Pair2 a b
或Pair1 (2,"hello")，它们都存储相同的数据。
鉴于此，我们可以将Pair2 2 "hello"的定义重写为：
Tree k v现在，data Tree k v = EmptyTree | Node k v (Tree k v) (Tree k v)
构造函数中的四个字段没有按此顺序排列；我们可以重新排序它们并仍然存储完全相同的信息，因此让我们将“左分支”字段移到最前面：
Node现在，这与您的data Tree k v = EmptyTree | Node (Tree k v) k v (Tree k v)
类型的结构完全匹配：
BT