At the end of my previous learn-Haskell post I was just finished using some lifters for monads for a log parser. The next part of the homework was to make a binary tree to hold the log messages. I think I made something similar in ML as part of Programming Languages on Coursera, and the types for the tree nodes were already defined, so this was fairly straightforward.
The main part to get right was inserting log messages in the correct order:
insert :: LogMessage -> MessageTree -> MessageTree
insert (Unknown _) t = t
insert m Leaf = Node Leaf m Leaf
insert _ (Node _ (Unknown _) _) = error "Invalid Node: a node must not contain Unknown"
insert m@(LogMessage _ t _) (Node l m2@(LogMessage _ t2 _) r) = case compare t t2 of
LT -> insertOnLeft
EQ -> insertOnLeft
GT -> Node l m2 (insert m r)
where insertOnLeft = Node (insert m l) m2 r
I could have done a few things differently – the error condition could be ignored, but it feels much better to include it so that I have a total function (as far as I understand function totality). I could also have taken a different approach to the last case, using an if then else such as if (t <= t2) then Node (insert m l) m2 r else Node l m2 (insert m r). This may be more readable, now that I think about it, since compare t t2 isn’t quite as intuitive about what is less than what. I could also probably have done something with guards, which might have been nicer.
One thing I would have liked to do is leave off the t in the first pattern, giving insert (Unknown _) = id, but this seems to make it incompatible with the other patterns.
As usual, I am sure there are some abstractions I could use over this code to make it simpler, but I am happy enough with this for now.
I ended up with a nice little function to build an ordered tree out of an unordered list of log messages:
build :: [LogMessage] -> MessageTree
build = build' Leaf
where build' = foldr insert
Looking at that now, I think I mustn’t have sat back and looked at it after I simplified the where clause, because I could as easily have written build = foldr insert Leaf, which is faster to comprehend.
Converting the ordered tree back to a list was straightforward – I’m not totally confident about the performance characteristics, but I doubt that is worth worrying about at this stage of my learning.
inOrder :: MessageTree -> [LogMessage]
inOrder = (`inOrder'` [])
where
inOrder' Leaf lst = lst
inOrder' (Node l m r) lst = inOrder' l (m : inOrder' r lst)