Skip to content

Instantly share code, notes, and snippets.

# alisdair/traversal.coffee Last active Dec 14, 2015

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 =  t3 = [2, , ] 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
Owner Author

### alisdair commented May 16, 2013

to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.