将元素添加到二叉树Haskell

Question

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

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

treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x Empty = Node 0 Empty x Empty
treeInsert x (Node height left a right)
 | x == a = Node height left x right
 | x < a = Node height (treeInsert x left) a right
 | x > a = Node height left a (treeInsert x right)

当我使用我的代码时，它什么也没做，就像递归仍在起作用

   tree = foldTree [1, 2, 3]
   tree
=> Node 1 (Node 0 Empty 2 Empty) 3 (Node 0 Empty 1 Empty)   
   tree = treeInsert 4 tree
   tree

我是Haskell的新手，有人可以帮忙吗？非常感谢。

Answer 1

通过写tree = treeInsert 4 tree，您定义了一个名为tree的新变量，该变量本身已定义。在Haskell中，所有变量都是不可变的，这意味着，一旦为tree分配了值，就无法为其分配新值。您可以做的是定义一个具有相同名称的new变量，但是tree正文中的tree = …指向自身。

因此，您可以使用新变量：

tree2 = treeInsert 4 tree

例如：

Prelude> tree = Node 1 (Node 0 Empty 2 Empty) 3 (Node 0 Empty 1 Empty) 
Prelude> tree2 = treeInsert 4 tree
Prelude> tree2
Node 1 (Node 0 Empty 2 Empty) 3 (Node 0 Empty 1 (Node 0 Empty 4 Empty))

但是看起来节点的“高度”没有正确更新。

在Haskell中使用变量本身并不常见，例如，您可以使用以下方法创建无限的零列表：

zeros = (0:zeros)