Pattern matching and Quicksort in Ruby

I was looking through an old gem that I needed to update for a project I’m on, and it had defined within it a partition method and a quicksort. I wanted to update it, but in my head I was wishing I could insert something as beautiful as this Haskell code:

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

I don’t really care about the type information, much as Haskellers like to rave on about it, I’m quite happy with Ruby’s duck typinghttp://news.ycombinator.com/item?id=3898999. I would, however, really like the where clause and the guards.

Ok, we don’t have the where clause in Ruby :( and no overloading of methods using guards :( but there is pattern matching! And I was surprised to find this wonderful, wonderful piece of matching today:

c,d,*e = [1,2,3,4,5,6]
# => [1, 2, 3, 4, 5, 6]
# => 1
# => 2
# => [3, 4, 5, 6]

This is excellent* and can be used to implement quicksort:

def quicksort( unsorted )
  fail ArgumentError, "Quicksort sorts lists!" unless unsorted.respond_to? :partition
  return [] if unsorted.empty?
  p,*xs = unsorted
  lesser, greater = xs.partition{|x| x < p }
  quicksort( lesser ) + [p] + quicksort( greater )

What do we have?

  • The raise… mimicks Haskell’s type information.
  • return is the termination clause (which I always write first when writing something recursive). Since in that case unsorted would equal [] you may wonder why I didn’t return unsorted. Simply because it’s quicker to read and comprehend what is actually happening, give an empty array and you get back an empty array.
  • Two lines of pattern matching wondrousness follow.
  • A bit of recursion.

Almost Haskell then :)

* by excellent, I mean it takes less lines to write what I mean to say - I find Ruby has an almost perfect mix of expressiveness with terseness. Hardly surprising that it came from Japan.