haskell - 在 Haskell 中实现二叉搜索树插入

Question

我正在实现 BST 的插入功能，下面是我的代码:

data Tree a = Empty | Branch a (Tree a) (Tree a) 
    deriving (Show, Eq)

tinsert             :: Tree a -> a -> Tree a 
tinsert Empty a         = Branch a Empty Empty
tinsert (Branch a left right) b
    | b == a = Branch a left right
    | b < a = Branch a (tinsert left b) right
    | b > a = Branch a left (tinsert right b)

当我在ghci中加载这个函数时，它给了我很多错误，这似乎与比较部分有关。我认为这没有任何问题。我是 Haskell 新手，有人可以帮忙吗？非常感谢。

Answer 1

更改 tinsert 的类型至

tinsert :: (Ord a) => Tree a -> a -> Tree a 

修复它。

这是必要的，因为函数 (<)和(>)来自Ord类型类，并且您需要在类型签名中承认这一点。

您还使用 ==和(==) :: Eq a => a -> a -> Bool ，但是Eq是 Ord 的父类(super class)，所以编译器知道如果你有 (<)您已经拥有 == ，所以你不需要说 Eq a也是如此。