CODEWITHSUNDEEP
haskellinsertbinary-search-tree
kornel kornel
kornel kornel

Reputation: 55

Add element to binary tree Haskell

I'm implementing the insert function of a BST, below is my code:

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)

When I use my code it doesn't do anything, like the recurrence is still working

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

I'm new to Haskell, could anybody help? Thanks a lot.

Upvotes: 1

Views: 1996

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476557

By writing tree = treeInsert 4 tree, you define a new variable named tree that is defined in trems of itself. In Haskell all variables are immutable, so that means that once tree is assigned a value, you can not assign it a new value. What you can do is define a new variable with the same name, but then tree in the body of tree = … refers to itself.

You thus can use a new variable:

tree2 = treeInsert 4 tree

For example:

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))

It looks like the "height" of the nodes is not properly updated however.

Using variables in terms of itself is not uncommon in Haskell, for example you can make an infinite list of zeros with:

zeros = (0:zeros)

Upvotes: 3

Related Questions