goodmike blogs here

Nathan Sanders‘ recent post about functional programming in Ruby includes some advice about not trying to force too much mapping and folding into Ruby. Here’s how he expresses it: “Ruby! OOP! Remember?”

But I couldn’t help myself. I spend a good deal of time these days in student mode, programming in scheme, and I really like the elegance of recursion, especially when it’s used on data structures that support recursion and iteration, like linked lists. So I indulged myself a bit while writing some practical Ruby code. I marked it mentally as something I would probably have to come back to and replace, but a funny thing happened. I still like it. I think it works really well.

Linking up a set of objects

Here’s the gist. I’m modeling grading systems for students. Each system has a set of possible grades (as in scores). Each grade has a letter value—a string like “A” or “B+”—and a range of number grades—92 to 98, or 88 to 90. Each student is being evaluated against some such set, and we’re assuming there could be more than one set (since the students go to different schools). So every grade has to have a string for the letter grade. But how about the number ranges?

When I imagined the process of matching a number score to a letter grade, it seemed simplest to give each grade a minimum number grade, a lower boundary. Each grade, starting with the highest one, is examined. If the score is higher than the grade’s minimum, then we’ve found the grade. If not, we should examine the next-highest grade. It’s an iterative process that could be handled with find. But, scheme-infected as I am, I decided to give each grade object a link to the next grade object. Then I could write recursive methods for the grade object with a classic scheme three-condition construct: 1) Is this the last object? Then we’re done. Return this object. 2) Is this the object that we’re looking for? Then return it. 3) Are there any more objects? Then try the next one.

Here’s the method. I’m sweating just a bit to expose this, since it may still prove to be stupid or naive, but nothing ventured means nothing gained.

  def letter_grade_for_number(grade)
    if @nxt.nil?
      self.letter_grade
    elsif grade >= self.min_number_grade
      self.letter_grade
    else 
      @nxt.letter_grade_for_number(grade)
    end
  end 

Enumeration in the data, not the methods

What I like about this setup is that there’s no enumeration code in the method. There’s no each or find and no blocks. The enumeration is built into the data structure. So each method like letter_grade_for_number can be constructed this way. The alternative, it seems to me, would involve repeating that enumeration code in each and every method. Not to mention kind of messy look-aheads or special cases that might arise in other methods.

There’s also an advantage in the way other objects use this grade object. The app I’m building will associate grade ranges with more than one kind of object. Instead of each of these client objects needing to maintain their own collections of grades and methods for arraying them and searching them, all they have to do is pass a message to an object, their grade object. All the searching and finding is encapsulated behind this single object. Doesn’t that feel more object-oriented?

Data Storage

The linked list is a bit more complicated than a simple array. You might think it’s tough to handle persistence. But not really. I defined a belongs_to/many ActiveRecord relationship between a client class and the grade range class. Once you’ve retrieved a set of grades, linking them together is this easy:

    ranges = ranges.sort_by(&:min_number_grade)
    ranges.inject(nil) {|prev_range, range|
      range.nxt = prev_range
      range
    }

The inject returns the final (highest-score) grade, which is the head of the linked list. Ruby’s functional capacities are considerable, and they make recursive and iterative operations natural.

Yeah, I know: O(n) no! growth!

Each recursive call to a @nxt object’s method means another method call on the stack and Theta-n growth for the memory space needed for the operation. I wouldn’t do this with a list that could have thousands of members. With a single grading system, however, I can be confident I’ll be handling a dozen or so at most.

Hybrid Languages

Last week I posted about learning how to program in an object-oriented fashion in scheme, about which one could say, “Lisp! Functional! Remember?” Using a recursive structure in Ruby turns out to be less exotic than one would think. I’m certainly not going to start programming in Ruby as if it were scheme (or vice versa), but I have decided to treat each as a hybrid language. One in which it’s probably easiest to use one style of programming 80% of the time; but in the remaining 20% of cases, it isn’t hard to do something else if you decide that would be best.