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

### Like this:

Like Loading...