This site provides the following access keys:

Brandan Lennox's

“To iterate is human…”

“…to recurse, divine.”

That’s one of maybe five of these fifty programming quotes I can recall at will. I actually used it today. Super proud about this one!

At work, our thing uses a tree structure with a Rails model like this:

class Node
  has_one :parent, :class_name => 'Node'
  has_many :children, :class_name => 'Node', :foreign_key => :parent_id
end

We needed the “path” from any given node back to the root of the tree. It was originally implemented as a named scope and an instance method that called that scope:

scope :path, lambda { |id| 
  {
    :select => 'parent.*',
    :joins => ', nodes AS parent',
    :conditions => ['nodes.left BETWEEN parent.left AND parent.right AND nodes.id = ?', id],
    :order => 'parent.left'
  }
}

def path
  self.class.path(id)
end

It’s was performing terribly on large data sets. Not only was the query performance bad, but we were only ever using the return value of the named scope as an array. There was no need for all the overhead of a named scope. We determined that it would actually be faster to hit the database n times for a node at depth n than to join all the ancestors in one query.

My first thought was to collect the node’s parents in a loop:

def path
  node = self
  parents = [node]
  while parent = node.parent
    parents.unshift parent
    node = parent
  end
  parents
end

It worked. Tests passed. Performance was astronomically better (down to 1ms from 270,000ms). I almost checked it in, but I hesitated. I heard the faint voice of L. Peter Deutsch, snickering at me in that way he almost certainly must.1 “Loops?” he said. “Gfaw.”

In about two minutes, I came up with this:

def path
  parent.path << self rescue [self]
end

Shit! I mean, the syntax might be a little wonky if you don’t read Ruby, but that’s magic. From a named scope with a lambda doing some kind of SQL query that stumped three professional programmers2 to one beautiful tail-recursive line. I’m patting myself on the back pretty hard!

Footnotes

  1. If your quip about programming made it into a well-known list, you probably snicker at bad programmers.
  2. I still don’t know why we were filtering by left and right values and an ID.