如何在Haskell中实现二叉搜索树

在Haskell中实现二叉搜索树（Binary Search Tree）可以使用自定义类型来表示树节点，然后使用递归函数来进行插入、查找、删除等操作。下面是一个实现二叉搜索树的示例代码：

-- 自定义二叉搜索树节点类型
data BST a = Empty | Node a (BST a) (BST a)

-- 插入元素到二叉搜索树
insert :: (Ord a) => a -> BST a -> BST a
insert x Empty = Node x Empty Empty
insert x (Node val left right)
  | x < val   = Node val (insert x left) right
  | x > val   = Node val left (insert x right)
  | otherwise = Node x left right

-- 从二叉搜索树中查找元素
search :: (Ord a) => a -> BST a -> Maybe a
search _ Empty = Nothing
search x (Node val left right)
  | x < val   = search x left
  | x > val   = search x right
  | otherwise = Just val

-- 从二叉搜索树中删除元素
delete :: (Ord a) => a -> BST a -> BST a
delete _ Empty = Empty
delete x (Node val left right)
  | x < val   = Node val (delete x left) right
  | x > val   = Node val left (delete x right)
  | otherwise = case (left, right) of
                  (Empty, Empty) -> Empty
                  (Empty, _)     -> right
                  (_, Empty)     -> left
                  (_, _)         -> Node (minimum right) left (delete (minimum right) right)

这个实现使用了自定义的二叉搜索树节点类型 BST，其中节点可以是空的 Empty，或者包含一个值和左右子树的 Node。在插入、查找、删除操作中，我们根据节点值的大小来决定在左子树或右子树进行递归操作。

可以使用以下代码来测试这个实现：

tree :: BST Int
tree = foldl (\acc x -> insert x acc) Empty [4, 2, 7, 1, 3, 6, 9]

main :: IO ()
main = do
  putStrLn "Binary Search Tree Example:"
  putStrLn "Inserting elements: 4 2 7 1 3 6 9"
  putStrLn "Searching for element 6:"
  putStrLn (show (search 6 tree))
  putStrLn "Deleting element 4:"
  let newTree = delete 4 tree
  putStrLn (show newTree)

输出结果会显示二叉搜索树的插入、查找和删除操作的结果。

这个实现只是二叉搜索树的基本操作，你还可以根据自己的需求进行扩展，例如添加其他辅助函数或在节点中存储其他信息。