Add element to binary tree Haskell

Question

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.

If you write tree = treeInsert 4 tree, you make a cycle, since you here define tree in terms of itself. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented May 30, 2020 at 13:20

willeM_ Van Onsem · Accepted Answer · 2020-05-30 13:29:09Z

3

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)

edited May 30, 2020 at 13:29

answered May 30, 2020 at 13:23

willeM_ Van Onsem

482k33 gold badges483 silver badges624 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Add element to binary tree Haskell

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related