[e-lang] Elegant DFS and BFS in E

[Jasvir Nagra]

Features of some programming languages make some algorithms more elegantly
expressly than others.  In a moment of frivolity I suggested to MarkM that
stack-based languages for example might favor depth-first over breadth-first
because it is easy to take advantage of the call stack instead of having to
allocate a new data structure to store a queue and that in a queue-based
language more people would use a breadth-first visitor.

Mark pointed out that E has two calling conventions - one that is stack-like
and one that is queue-like which makes both styles of visitors pleasantly
expressible (slightly modified to emphasize the similarity):

def breadth(tree, visit) {
  for child in tree.children() {
    breadth<-(child, visit)
  }
  visit(tree)
}

def depth(tree, visit) {
  for child in tree.children() {
    depth(child, visit)
  }
  visit(tree)
}

I realize its not really much more to allocate a queue but its a pretty
pattern and makes it particularly easy to mix DFS and BFS.

-- 
Jasvir Nagra
http://www.cs.auckland.ac.nz/~jas <http://www.cs.auckland.ac.nz/%7Ejas>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.eros-os.org/pipermail/e-lang/attachments/20090610/cec823c2/attachment.html