Pattern Matching in Ruby

by

for the impatient:[tests]
To paraphrase Alan Perlis, learning a good programming language should affect the way you think about programming. The only problem: since it’s such a good language, it’ll probably give you a bad case of feature envy when you use other languages.
Case in point: Pattern matching in Haskell (Yeah, I know, other languages have pattern matching, but Haskell introduced me to the concept). Pattern matching let’s you write very clear code by choosing an execution path based on the structure of a function’s arguments. So, for instance, you can write:

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Instead of checking the argument within the function, you essentially write three versions of the function ‘fib’ – one for when the argument is 0, one for when the argument is 1, and one for all other cases.
Now this may just seem like a fancy switch statement, but it’s much more powerful than that. For instance, pattern matmching can break down lists. Check out the Haskell implementation of map.

map _ []     = []
map f (x:xs) = f x : map f xs

What’s going on here? Remember, map is a function that takes a function and a list and applies the function to each member of the list. The _ is like a wild card – it matches anything. The [] stands for the empty list. So, if the arguments to ‘map’ are an empty list and ANY function, it just returns an empty list.
Otherwise, Haskell binds the first element of the list to the name ‘x’ and the remainder of the list to the name ‘xs’. It then applies the function to x and recursively calls ‘map’ on the remainder of the list. Very cool!
As you can see, pattern matching can really simplify methods, especially when the arguments to the method have complex structures (if you’re still not convinced, Steve Yegge motivates pattern matching much better than I have). The trouble is, I don’t use Haskell on a regular basis – I use Ruby. And Ruby doesn’t have pattern matching.
Luckily, Ruby is a remarkably flexible language. So much so that a number of people have implemented various versions of pattern matching in Ruby. But while those implemenations are very cool and taught me a lot, none of them quite felt right. Plus, I’d been looking for an excuse to play around with Ruby’s metaprogramming features and this seemed like a good opportunity.
So, I wrote my own version of pattern matching in Ruby. The Fibonacci sequence looks like this:

def fib(n)
match n do
with(0) {0}
with(1) {1}
otherwise {fib(n-1) + fib(n-2)}
end
end

(Although this isn’t really a great example because a case statement would suffice). And map looks like this:

def map(proc,arr)
match([proc,arr]) do
with([:_,[]]) {[]}
with([:f,:x % :xs]) { [f.call(x)] + map(f,xs) }
end
end

It’s not quite as succinct as the Haskell code, but it’s reasonably close (note that I can’t use Haskell’s : operator to destructure the list, so I use the % operator instead).
Here’s a more interesting, if contrived, example – let’s say you have a tree structure (represented by nested arrays). Each node has a left and right branch as well as an operator. So a tree might look like this:
[[5,'*',10],'+',[6, '/', 3]]
Now let’s write a method that will give us a string representation of any tree. So, for the example above, we’d want “((5 * 10) + (6 / 3))”. Without pattern matching, we’d write something like this:

def disp(tree)
if(tree.is_a?(Fixnum))
tree
elsif(tree.is_a?(Array) && tree.length==3 && tree[1].is_a?(String))
"(#{disp(tree[0])} #{tree[1]} #{disp(tree[2])})"
else
"Invalid tree structure"
end
end

but with pattern matching, we can write:

def disp(tree)
match tree do
with(:num & Fixnum) {num}
with([:left, :op & String, :right]){"(#{disp(left)} #{op} #{disp(right)})"}
otherwise {"Invalid tree structure"}
end
end

Let’s go through this step by step. If ‘tree’ is a Fixnum, we assign bind it to the name ‘num’ and return it (the & operator binds the matching argument to the symbol on its left – in this case, :num). If ‘tree’ is actually a tree node, we give a name (‘left’, ‘op’, and ‘right’) to the various parts of the node and recurse. Once you get past the strange looking syntax, the code is much cleaner and easier to understand than the version without pattern matching.
We can also destructure arrays. Here’s an example that drops the first three elements of an array:

def drop_three(array)
match array do
with(:_ % :_ % :_ % :xs) { xs }
end
end

If you’d like more examples, the tests are a good place to start. Or you can just check out the source code. Feel free to use it however you want – I’d love it if a better Ruby hacker than I improved this stuff…
A few caveats:

  • I really can’t take much credit for this, my code is heavily depedent on some very nice DSL and let code written by Reginald Braithwaite. It’s cool stuff, check it out.
  • This was my first attempt at some serious Ruby metaprogramming. I probably did some dumb stuff – so if you have any tips, please let me know.
  • It’s pretty darn slow right now. If anyone wants to take a crack at speeding it up, be my guest. I’ll probably look into it as time permits.

Thanks and enjoy!

Advertisements

5 Responses to “Pattern Matching in Ruby”

  1. Eric Says:

    Nice article Ben! Better than what I did.
    I wrote my blog entry before using a language having pattern matching capabilities (Scala). Now I appreciate all the more the concept but I also I can see how it is really linked to Type definitions.
    Since types are very different in Ruby you have to add syntactic elements to reproduce type constructors. On the other hand, types are much more malleable in Ruby, so I think it may also be interesting to add pattern matching based on respond_to? calls, don’t you think?
    Eric.

  2. Jeremy Voorhis Says:

    For another example of pattern matching in Ruby, see the Ruby Code & Style article at http://www.artima.com/rubycs/articles/patterns_sexp_dsls.html

  3. Ben Says:

    Eric,
    Glad you enjoyed the article – I certainly enjoyed (and learned a lot from) yours.
    You’re absolutely right about pattern matching and types. The more I worked on this project, the more I realized that a lot of the good examples of pattern matching in Haskell depended on the type system – and I couldn’t see how that would translate to Ruby.
    For instance, pattern matching is really useful in Haskell in code like this:
    colorToRGB Orange = (255,128,0)
    colorToRGB Yellow = (255,255,0)
    colorToRGB Green = (0,255,0)
    colorToRGB Blue = (0,0,255)
    colorToRGB Purple = (255,0,255)
    colorToRGB White = (255,255,255)
    colorToRGB Black = (0,0,0)
    colorToRGB (Custom r g b) = (r,g,b)
    but it wasn’t clear to me how to get something similarly useful with Ruby’s type system.
    So, I sort of cheated – I only worked on pattern matching based on values, types (via is_a? calls), and array structure.
    Your idea of doing pattern matching based on respond_to? calls is very, very interesting. I’ll think about it some more and see if I can some up with some decent syntax.
    Thanks for the ideas!
    Ben

  4. A. Rubio Says:

    Hi,
    very cool implementation for pattern matching. I’ve been reading your tests and running some code. I have a small doubt. Can you refactor the following code to have only two matches?:
    def dummy(p)
    match(p) do
    with(Foo) { 1 }
    with(Bar) { 1 }
    otherwise { 2 }
    end
    end
    I couldn’t find how to do it.
    Thanks!

  5. Ben Says:

    Unfortunately, you can’t – I couldn’t think of a clean syntax to express the condition of p being a Foo or a Bar.
    More generally, you can’t express any OR conditions within the same match (for instance, you couldn’t match on being p being equal to ‘a’ or ‘b’ either). I think in practice this isn’t too much of a limitation – but I could be wrong!
    I haven’t actually tried it out, but you might be able to extend this syntax like so:
    def dummy(p)
     match(p) do
     with(Foo).or(Bar) { 1 }
     otherwise { 2 }
     end
    end

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: