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.

Owner

alisdair commented May 16, 2013

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