Instantly share code, notes, and snippets.

Embed
What would you like to do?
Tom Moertel's tree traversal ported from Haskell to Coffeescript.
# Translation of Tom Moertel's tree traversal:
#
# http://blog.moertel.com/posts/2012-01-26-the-inner-beauty-of-tree-traversals.html
t0 = []
t1 = [1]
t3 = [2, [1], [3]]
preorder_traversal = (f, z, tree) ->
do go = (tree, z) ->
return z unless tree?
[v, l, r] = tree
z1 = f(v, z)
z2 = go(l, z1)
z3 = go(r, z2)
inorder_traversal = (f, z, tree) ->
do go = (tree, z) ->
return z unless tree?
[v, l, r] = tree
z1 = go(l, z)
z2 = f(v, z1)
z3 = go(r, z2)
flatten = (traversal, tree) ->
append = (i, a) -> a.concat(i)
traversal append, [], tree
console.log flatten inorder_traversal, t3
console.log flatten preorder_traversal, t3
curry = (f, a) -> (x) -> f(a, x)
traverse = (step, f, z, tree) ->
do go = (tree, z) ->
return z unless tree?
[v, l, r] = tree
step curry(f, v), curry(go, l), curry(go, r), z
preorder = (f, z, tree) -> traverse(((n, l, r, x) -> r l n x), f, z, tree)
inorder = (f, z, tree) -> traverse(((n, l, r, x) -> r n l x), f, z, tree)
postorder = (f, z, tree) -> traverse(((n, l, r, x) -> n r l x), f, z, tree)
console.log flatten preorder, t3
console.log flatten inorder, t3
console.log flatten postorder, t3
leftorder = (f, z, tree) -> traverse(((n, l, r, x) -> l n x), f, z, tree)
rightorder = (f, z, tree) -> traverse(((n, l, r, x) -> r n x), f, z, tree)
treemin = (tree) -> leftorder Math.min, Number.MAX_VALUE, tree
treemax = (tree) -> rightorder Math.max, -Number.MAX_VALUE, tree
console.log treemin t3
console.log treemax t3
@alisdair

This comment has been minimized.

Copy link
Owner Author

alisdair commented May 16, 2013

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment