A simple Tree data structure in Haskell


This is part of my attempt to learn Haskell in a proper manner. I have been on and off learning Haskell for quite a few years now, always getting interrupted for some reason. This time, I decided to bite the bullet and get on with it!

As part of that, I started off with my favourite Haskell textbook, Professor Graham Hutton’s “Programming in Haskell”, 2nd Edition. This is arguably THE book that opened my eyes to Functional Programming in general. This book is almost perfect with one small flaw, in my opinion, of course. The bottom-up approach of solving problems is excellent, but it would have been rather nice if a small synopsis of the problem and the proposed approach were given at the beginning instead of having to read the whole code to understand it.

Having finished around half of that book, I realised that it was a bit short on examples, problems, and the downright dirty parts of Haskell, introducing IO only around the middle of the book. That’s when I decided to go for Allen and Moronuki’s book, “Haskell Programming from First Principles” to get up to speed on actual real-world programming in Haskell. The first few chapters are extremely basic (and I do find the tone a bit too prescriptive and pedantic, but that should suit a complete beginner just fine. For practice and hands-on though, it is a most excellent resource.

As part of my reboot of Haskell, I decided to implement a small Tree data structure in Haskell, all with the express aim of getting rid of the cobwebs. I can’t say that I’m too happy with my first attempt even though it clearly works more or less as expected. It feels very rough and creaky and the Null vs Leaf issue is pretty irritating as well. Well, after some more practice, I should be able to start iterating on better versions!

For now, here’s the code. It’s pretty much self-explanatory. The basic Tree type (single type parameter for now!), a helper function to create a Binary Search Tree (easier to confirm the output using preorder traversal), and the three standard binary tree traversal algorithms.

{- A binary tree implementation -}

data Tree a = Null | Leaf a | Node (Tree a) a (Tree a)  deriving Show


createNode :: a -> Tree a
createNode value = Leaf value 


addNode :: (Ord a) => Tree a -> a -> Tree a
addNode tree value = case tree of
                        Null -> createNode value
                        Leaf x -> if value <= x then
                                    Node (createNode value) x Null
                                  else
                                    Node Null x (createNode value)
                        Node l n r -> if value <= n then
                                        Node (addNode l value) n r
                                      else
                                        Node l n (addNode r value)

makeBST :: Ord a => [a] -> Tree a
makeBST [] = Null  
makeBST (n:ns) = addNode (makeBST ns) n
                     


-- inorder traversal (left, root, right)
inorder :: Tree a -> [a]
inorder tree = case tree of
                 Null -> []
                 Leaf x -> [x]
                 Node l n r -> inorder l ++ [n] ++  inorder r


-- preorder traversal (root, left, right)
preorder :: Tree a -> [a]
preorder tree = case tree of
                  Null -> []
                  Leaf x -> [x]
                  Node l n r -> [n] ++ preorder l ++ preorder r


-- postorder traversal (left, right, root)
postorder :: Tree a -> [a]
postorder tree = case tree of
                   Null -> []
                   Leaf x -> [x]
                   Node l n r -> postorder l ++ postorder r ++ [n]

A sample run:

*Main> let bst = makeBST [10,18,12,7,10,11,3,4,4,-2,-3,100]
*Main> bst
Node (Node Null (-3) (Node Null (-2) (Node (Node (Leaf 3) 4 Null) 4 (Node (Node (Node Null 7 (Leaf 10)) 10 Null) 11 (Node Null 12 (Leaf 18)))))) 100 Null
*Main> inorder bst
[-3,-2,3,4,4,7,10,10,11,12,18,100]
*Main> preorder bst
[100,-3,-2,4,4,3,11,10,7,10,12,18]
*Main> postorder bst
[3,4,10,7,10,18,12,11,4,-2,-3,100]
*Main> 

Ah well, it’s quite exciting to see something working as expected, isn’t it? Well, onwards then with Haskell (and then on to Agda and Idris, which I am very much interested in for edificational purposes!)

Advertisements
A simple Tree data structure in Haskell

Speak your mind!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s