The inner beauty of tree traversals
Posted by Tom Moertel Fri, 27 Jan 2012 04:24:00 GMT
This has been done a million times before, but if you haven’t seen it, it’s pretty neat. Let’s say you have a simple recursive data structure like a binary tree:
module Tree where
data Tree a = Empty
| Node a (Tree a) (Tree a)
deriving (Eq, Show)
-- some binary trees
t0 = Empty
t1 = Node 1 Empty Empty
t3 = Node 2 (Node 1 Empty Empty) (Node 3 Empty Empty)
Now say you want to traverse the nodes, in “preorder.” So you write a traversal function. It folds a binary operator f through the values in the tree, starting with an initial accumulator value of z. First, it visits the current node, then the left subtree, and finally the right subtree, combining each value it encounters with the current accumulator value to get the next accumulator value. The final accumulator value is the result.
Spelling out the steps, it looks like this:
preorder_traversal f z tree = go tree z
where
go Empty z = z
go (Node v l r) z = let z' = f v z -- current node
z'' = go l z' -- left subtree
z''' = go r z'' -- right subtree
in z'''
But if you wanted an “inorder” traversal instead, you’d write a slightly different function, visiting the left subtree before the current node:
inorder_traversal f z tree = go tree z
where
go Empty z = z
go (Node v l r) z = let z' = go l z -- left subtree
z'' = f v z' -- current node
z''' = go r z'' -- right subtree
in z'''
To see how the two traversal functions work, let’s use both to flatten the 3-node tree t3 we defined earlier.
flatten traversal = reverse . traversal (:) []
test0i = flatten inorder_traversal t3 -- [1,2,3]
test0p = flatten preorder_traversal t3 -- [2,1,3]
Great.
But now you start thinking about post-order traversal. Do you want to write a third traversal function that’s almost the same as the first two?
So you go back to the inorder traversal and start staring real hard at that let statement. Can you rewrite it? Yes:
inorder_traversal2 f z tree = go tree z
where
go Empty z = z
go (Node v l r) z = go r . f v . go l $ z
And now you’ve got it. Just by reordering the applications of (go l), (f v), and (go r), you can control the traversal.
Which leads to a general traversal function that lets some other function control that ordering:
traverse step f z tree = go tree z
where
go Empty z = z
go (Node v l r) z = step (f v) (go l) (go r) z
Doesn’t that look beautiful?
Now you can just spell out your desired traversals:
preorder = traverse $ \n l r -> r . l . n
inorder = traverse $ \n l r -> r . n . l
postorder = traverse $ \n l r -> n . r . l
A test drive:
test1p = flatten preorder t3 -- [2,1,3]
test1i = flatten inorder t3 -- [1,2,3]
test1o = flatten postorder t3 -- [1,3,2]
And you’re happy.
But can you go further? What if your trees are binary search trees and you just want to find the minimum or maximum value? Can you just traverse to the left or right?
Yes:
leftorder = traverse $ \n l r -> l . n
rightorder = traverse $ \n l r -> r . n
treemin = leftorder min maxBound
treemax = rightorder max minBound
test2l = treemin t3 :: Int -- 1
test2r = treemax t3 :: Int -- 3
Isn’t that neat?
I’ve just been reading on using the memoisation functions and writing your function as a generator so you can use fix e.g.
fibs’ f n = f (n – 1) + f (n – 2)
Then you can compose that inner ‘f’
fibs = fix (memo . fibs’)
To make an efficient version. Seems a very similar kind of practice.
Cheers – Oliver
Your inorder_traversal2 function is where I expected to see postorder_traversal, which confused me until I went back to read the name.
@Mike B: Thanks for letting me know about the confusing transition. I’ve edited the article to make it clearer. Thanks!
I was very glad to see this. Taking this approach to much of the data manipulation code at work really saved my bacon yesterday when I was suddenly required to add a new export format for our scheduling information. Thanks to the genericity of the export code we already had, it turned out to be a relatively straightforward job and two hours later it was in the hands of the people who needed it.
I’m increasingly of the opinion that it’s always worth thinking like this. Okay so the application at work is written in C# and F#, but the principles still apply.
Thank you! I’ve never seen this and often wondered whether it was possible.