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 = Empty t0 = Node 1 Empty Empty t1 = Node 2 (Node 1 Empty Empty) (Node 3 Empty Empty)t3
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:
= go tree z preorder_traversal f z tree where Empty z = z go Node v l r) z = let z' = f v z -- current node go (= go l z' -- left subtree z'' = go r z'' -- right subtree z''' 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:
= go tree z inorder_traversal f z tree where Empty z = z go Node v l r) z = let z' = go l z -- left subtree go (= f v z' -- current node z'' = go r z'' -- right subtree z''' in z'''
To see how the two traversal functions work, let’s use both to flatten the 3-node tree t3 we defined earlier.
= reverse . traversal (:)  flatten traversal = flatten inorder_traversal t3 -- [1,2,3] test0i = flatten preorder_traversal t3 -- [2,1,3]test0p
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 looking real hard at that let expression. Can you rewrite it? Yes:
= go tree z inorder_traversal2 f z tree where Empty z = z go Node v l r) z = go r . f v . go l $ z go (
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 Empty z = z go Node v l r) z = step (f v) (go l) (go r) z go (
Doesn’t that look beautiful?
Now you can just spell out your desired traversals:
= traverse $ \n l r -> r . l . n preorder = traverse $ \n l r -> r . n . l inorder = traverse $ \n l r -> n . r . lpostorder
A test drive:
= flatten preorder t3 -- [2,1,3] test1p = flatten inorder t3 -- [1,2,3] test1i = flatten postorder t3 -- [1,3,2]test1o
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?
= traverse $ \n l r -> l . n leftorder = traverse $ \n l r -> r . n rightorder = leftorder min maxBound treemin = rightorder max minBound treemax = treemin t3 :: Int -- 1 test2l = treemax t3 :: Int -- 3test2r
Isn’t that neat?