Добавить элемент в двоичное дерево 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 присвоено значение, вы не можете присвоить ему новое значение. Что вы можете сделать, так это определить новую переменную с тем же именем, но тогда tree в теле tree = … ссылается на себя.

Таким образом, вы можете использовать новую переменную:

<b>tree2</b> = 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, например, вы можете составить бесконечный список нулей с помощью:

<b>zeros</b> = (0:<b>zeros</b>)