Haskell hacks
4 December 2007Here you go, a binary search tree in Haskell in ~70 lines
Haskell is really nice to program with, because is challenging and you usually don’t get stuck in annoying bugs (pure functional languages don’t have side effects).
Branch this hack (and more, if I get into it!) at: http://bzr.geeksynapse.net/haskell/
C’mon, hurry up, all the cool guys program in haskell now
module BinaryTree where
data BT = L | N Int BT BT deriving Show
-- Creates an empty tree
empty :: BT
empty = L
depth :: BT -> Int
depth L = 0
depth (N _ t u) = (max (depth t) (depth u)) + 1
weight :: BT -> Int
weight L = 0
weight (N _ t u) = (weight t) + (weight u) + 1
inorder :: BT -> [Int]
inorder L = []
inorder (N v t u) = inorder t ++ [v] ++ inorder u
left :: BT -> BT
left L = L
left (N _ t _) = t
right :: BT -> BT
right L = L
right (N _ _ u) = u
-- Yija... code reuse
btmin = head . inorder
btmax = head . reverse . inorder
-- Tricky: we return a binary list with the route to the node
search :: BT -> Int -> Maybe [Int]
search L s = Nothing
search (N v t u) s
| v == s = Just []
| (search t s) == Nothing && (search u s) == Nothing = Nothing
| (search t s) /= Nothing = fmap ((:) 0) (search t s)
| (search u s) /= Nothing = fmap ((:) 1) (search u s)
getelem :: BT -> [Int] -> Maybe Int
getelem L _ = Nothing
getelem (N v _ _) [] = Just v
getelem (N v t u) (x:xs)
| x == 0 = getelem t xs
| otherwise = getelem u xs
-- Inserting an existing item does nothing
insert :: BT -> Int -> BT
insert (L) i = (N i L L)
insert (N v t u) i
| i < v = (N v (insert t i) u)
| i > v = (N v t (insert u i))
| otherwise = (N v t u)
– In case of deleting a 2-leaf node, we use the left or righ node to replace
– depending on the depth of the tree (so we try to keep it balanced)
delete :: BT -> Int -> BT
delete (L) d = (L)
delete (N v L L) d
| v == d = L
| otherwise = (N v L L)
delete (N v t L) d
| v == d = t
| otherwise = (N v (delete t d) L)
delete (N v L u) d
| v == d = u
| otherwise = (N v L (delete u d))
delete (N v t u) d
| v == d && depth t > depth u = (N (btmax t) (delete t (btmax t)) u)
| v == d = (N (btmin u) t (delete u (btmin u)))
| otherwise = (N v (delete t d) (delete u d))
6 Responses to “Haskell hacks”
December 4th, 2007 at 6:32 pm
code reuse is good, but it’s a bad idea here. btmin will run in O(log n) time because haskell is lazy, whereas btmax will run in O(n) time because reverse will force the whole inorder list to be traversed to find the end. Better to do it write, (or parameterize inorder so that it can do it backward).
Kyle.
December 4th, 2007 at 6:39 pm
Good point there. I didn’t analyze the performance of this yet, I’ll fix it in the bzr tree.
Thanks for the tip!
December 4th, 2007 at 11:04 pm
At first, let me say that I don’t know how to test your program! Do I need compile the source? Do I need an interpreter? How can I write my Haskell programs?
About Haskell… I had listened about it, but I never had seen it. So, I’ve been reading a bit about this programming language and the functional programming and I think that’s an interesting concept.
I can’t say any more at the moment, I must read much more about the functional paradigm and Haskell.
PS: It’s a good surprise seeing a new post in your page.
PS2: Please, forgive all my English mistakes (Spanish education!), I hope to have improved my English level, but…
December 4th, 2007 at 11:16 pm
You could either use hugs or ghc. Both have interpreter and compiler. Helium is the one I used at my university, but didn’t seem a good option on OS X. To write your own programs… you just need your text editor : P: After that you run the programs on the interpreter and cross your fingers.
If you are completely lost, check this tutorial (don’t worry, MS doesn’t own Haskell ;)
http://research.microsoft.com/~simonpj/papers/haskell-tutorial/index.htm
Hopefully, I’ll be adding the balanced version of the tree tomorrow. I’ve just finished the insertion, but the deletion is missing. Nevermind, tomorrow I have to work : P
PS: I also do mistakes in english, but I just don’t care, they probably get what I’m talking about ;). And they do mistakes too!! (just look at those poor kids at the spelling contests)
December 5th, 2007 at 1:01 am
I prefer:
data Tree = Leaf | Node !Int Tree Tree
That is, a lazy spine on the tree, but strict in the elements. When compiled with ghc -O2 -funbox-strict-fields (as discussed in this thread, you get good speedups over the fully lazy tree, and way better than the fully strict tree.
December 5th, 2007 at 10:21 pm
Your data constructors are a bit confusing, I think. By some definition, binary tree is empty(no nodes) or it has a root node and left and right binary trees. So data BT = Empty | Node Int BT BT might be better. At least it has consequences on depth/height -function.
depth Empty = 0 (or perhaps even Nothing)
depth (N _ Null Null) = 0
depth (N _ l r) = 1 max (depth l) (depth r)
Depth of root is zero.