05 5 / 2013

## Pattern Matching Re-Visited with the Prime Factors Kata

So I thought I had a good handle on pattern matching with my last blog post, but realized late last week that I really only understood a small portion of it so here’s more explanation and examples on pattern matching.

Before I launch into details, I just wanted to say that, based on what I learned last week when working on my Kata, I highly recommend learning Erlang before learning Elixir. If you understand Erlang, you will understand Elixir. And if you’re looking for help on Elixir, don’t bother googling it. You won’t find much these days. Google Erlang instead.

We had an Software Craftsman meeting the other night after work and were tasked with solving the Bowling Game Kata using Erlang. It was my first time really playing with and understanding Erlang, but I quickly got lost as I’ve never done the Bowling Game Kata before (hell, I think I’ve only bowled about 10 games in my entire life and certainly never tried to understand the scoring system). So instead, I pulled up a chair and sat beside a more experienced craftsman Justin and “helped” him come up with his solution (not really).

At the time, he happened to have an Erlang book sitting beside him and, at one point, reached to look up pattern matching in the book. And, viola…two whole pages about pattern matching that I had never seen before!

The puzzle pieces started to come together for me in that moment. Now, to REALLY complete my Kata using pattern matching (which Paul asked me to do probably 10 times - I just didn’t understand what he meant).

The Kata I did was the Prime Factors Kata and I only needed to factor four numbers to build the entire algorithm:

1, 2, 4 and 6

Crazy, eh?

First thing to know is that you can match on a value (which looks like an argument) like this:

def factor(1) do [] end

The way this method works is that when factor, with “1” being the argument, is called, this method will be executed and return []. That’s it! It’s specifically looking for a 1. No other calls to factor will be evaluated with this method.

Next, I can do something like this:

def factor(1) do [] end def factor(composite_number) do [composite_number] end

Notice anything weird about the code above? You probably see it. I have the same method name for both methods. But, just like in my other blog post on pattern matching, this is acceptable and will compile. What happens in this case is that if factor(1) is called, the first method will execute. If factor(10) is called, the second method will execute. Technically speaking, any other value of composite_number except for 1 will be evaluated using the second method.

Now a word of caution here that method ordering is important. If I were to reverse the order of the methods, the second method would never be executed:

def factor(composite_number) do [composite_number] end def factor(1) do [] end

The reason for this is because when calling the factor method, the processor starts at the top of the module working down until it finds a method that fits the bill. As soon as it finds the factor(composite_number) when callling factor(1), it will use that method instead and the factor(1) method would never be called.

The code above gets us through the factorization of 1 and 2. Next up is factoring 4:

def factor(1) do [] end def factor(composite_number) do [composite_number] end def factor(composite_number, primes) do factor(div(composite_number, 2), primes ++ [2]) end

This adds a third method that will start to divide numbers by 2 and assimilate the factors. Since the method now needs to return a list of values (in this case, [2,2]), I added an accumulator called “primes”. The code above doesn’t work for all tests yet. Here’s the fully-fuctional code:

def factor(composite_number) do factor(composite_number, []) end def factor(1, primes) do primes end def factor(composite_number, primes) do factor(div(composite_number, 2), primes ++ [2]) end

Two things I did in this step were to flesh out the original 2 methods and move the second method to the top of the heap. In Elixir (and maybe other functional languages as well?), if I didn’t move the second method to the top of the module, I would get a warning that the factor(composite_method) came after the factor(1, primes). My guess is because the factor(1) method needs two arguments and the other method did not. Sandro, one of the other 8th Light apprentices guessed that methods with the same number of arguments should be grouped together. Logically, it makes sense to move the factor(composite_number) to the top anyways as it is the point of entry for the function now.

The reason behind fleshing out factor(1) is that since we’re now initializing primes with a value of [], we can just return that for instead of hard-coding that method. That makes sense.

That leaves the factor(composite_number) method. Why did I flesh this method out the way I did? The reason is that since 1 was going to be evaluated with the factor(1, primes) method, that only left the 2 and 4 scenarios, both of which were divisible by 2. So, I morphed the factor(composite_number) method to become an “entry point” to the module and tacked on the initialized accumulator. That left the third method to handle the real (recursive) work.

Next up, numbers with factors other than 1 and 2…like 6. First, here’s the new method (at the bottom) that’s gonna get ‘er done:

def factor(composite_number) do factor(composite_number, []) end def factor(1, primes) do primes end def factor(composite_number, primes) do factor(div(composite_number, 2), primes ++ [2]) end def factor(composite_number, divisor, primes) do factor(composite_number, divisor + 1, primes) end

Along with a new method, there’s also a new argument that has to be incorporated in a few more places and initialized. Here’s the final version:

def factor(composite_number) do factor(composite_number, 2, []) end def factor(1, _, primes) do primes end def factor(composite_number, divisor, primes) when rem(composite_number, divisor) == 0 do factor(div(composite_number, divisor), divisor, primes ++ [divisor]) end def factor(composite_number, divisor, primes) do factor(composite_number, divisor + 1, primes) end

Changes to this set of methods are the new method, which will now be the core processing method. I added a guard statement to the third statement (the “when” clause). This will grab any calls to factor that are divisible by two but will skip over all the rest. The “1” class is still up there, ready to do the finishing job on any prime number where all the factors have been found and the last clause will just continue cycling through the divisors until it either a. finds all the relevant factors or b. increments up the the prime number itself (if there are no factors).

That’s the final solution that I came up with and presented at 8th Light for my first live Kata (ever). Speaking of which, what a nerve-wracking experience! But once it was over, I was relieved, proud of myself and felt a huge weight being lifted off my shoulders (and maybe a little disappointed with all the typing mistakes but I think that will get better with time and experience of performing in front of others).

Afterwards, Corey Haines issued me a challenge (at least I took it as one) to avoid making so many changes with each test. Instead, his suggestion was to do the minimal amount of work to get that one test to pass (even if it included making other methods). Once the new test was green, then re-factor down to my solutions that I showed above. Makes sense. Hmmm….just finished *Extreme Programming Explained* by Kent Beck where the words “red, green, refactor” just have been mentioned 20 times. You would think I would get it by now!

So that’s my next post. Seeing if I can take smaller steps on this Kata.