Harrison Lucas

@harry_dev

Elixir for Rubyists: Pattern matching and Recursion

Note: This was taken from my blog over at http://www.weeklycommit.com

This blog post series is going to go through the basics of Elixir for someone coming from the Ruby programming language.

Why?

Well from the outside, Elixir and Ruby look very similar syntactically. However, that is all they really share in common.

When you start using Elixir you will realise how different the two langauges are, I mean for starters, Elixir is a functional programming language where as Ruby is object orientated (although it can be argued that Elixir is the most Objected Oriented language out of them all, but that’s an argument for another time).

This series isn’t going to look at the reasons why one would want to use Elixir over Ruby, but if you want to get an idea, check out these posts:

Pattern Matching

Alright so with that out of the way lets jump into one of my favorite features of Elixir — pattern matching.

If you have never used pattern matching before, be warned, once you start, you can’t go back.

At it’s very simplest form, pattern matching is a way to destructure complex data types.

But what does that mean?

Well with an example, let’s say you had a map (the Elixir equivalent of a Ruby Hash {key: "val"}):

%{age: 22, name: "Harry"}

How would you go about getting the value of the :name key?

In ruby, you might do something like this:

person = {name: "harry", age: 22}  
person[:name]
# => "harry"

However, in Elixir you could do this instead:

%{name: name} = %{age: 22, name: "Harry"}
name
# => "Harry"

The reason this works is because that the = operator in Elixir doesn't mean assign, but rather match. Therefore the above statement is saying:

Make %{name: name} match %{age: 22, name: "Harry"}.

So how does it do this?

Well the process is something like this:

  1. It see’s that both the left and right hand side are the same data type (maps)
  2. It then see’s that both maps have a key called :name so they match
  3. It then notices that the map on the left does not have a value for the :name key however, the map on the right does have a value. Therefore, it must mean that name is the same as "Harry".

Another way to think of it is like algebra. E.g.

1 + x = 1 + 2

What’s the value of X?

2

But you can do even more then that. Let’s say that with the above, we wanted to have another person and see if it was the same as the second one. In Ruby, you might do something like this:

person = {name: "harry", age: 22}  
person2 = {name: "glen", age: 33}
person[:name] == person2[:name]

With Elixir, you could do this instead:

%{name: name} = {age: 22, name: "harry"}
%{name: ^name} = {age: 33, name: "glen"}
# => Error. No match on right hand side....

What we are doing here is using the ‘pin’ operator. This is basically saying, that we matched the value of name to a particular value before, so use that value instead of trying to match against a new one.

The benefits of this may not be obvious straight away. However, for me the power of pattern matching really shines when writing functions.

Let’s say you have a method that takes in a hash and multiplies two numbers together, only if they are equal. One implementation in Ruby could be:

def multiply_equal(n1, n2)  
raise "Not equal" if n1 != n2
n1 * n2
end

Pretty simple.

However, we can do better.

In Elixir, using pattern matching you could instead do something like this:

def multiply_equal(x,x) do  
x * x
end
def multiply_equal(_,_) do  
raise "Not Equal"
end
# or in one line
def multiply_equal(x,x), do: x * x  
def multiply_eqaul(_,_), do: raise "Not Equal"

So what’s going on here? It might not be evident at first but one thing to note, is that in elixir, you can define a function multiple times.

In the above example, we are defining two, two argument multiply_equal functions. The first function, will only ever be invoked if both arguments are the same, the second function, will be invoked for every other combination of two arguments.

Since a variable can only have one value, when we define a function head with the same two arguements e.g. (x,x) we are saying that this function is only ever to be invoked, if both arguments are the same. It makes no assumptions about the data types that get passed in.

E.g., these will all be invoked by the first function head

multiply_equal( [1,2,3,4], [1,2,3,4] )  
multiply_equal( "foo", "foo" )
multiply_equal( 'N', [78] )

(click here to see why that last one matches)

The benefits of this might not be immediately clear, but trust me, as you dive more and more into Elixir and Phoenix you will come to love this more then life itself.

Putting it all together

To illustrate how pattern matching and recursion can be used together we are going to work through creating our own multiply function.

Basically, we are going to replicate the * function common in most languages.

Now, it took me longer then I would like to admit to realise that multiplication is just addition, multiple times.

So how can we go about creating this using pattern matching and recursion?

Well do this, we are going to define 2 functions. In elixir, if a function has the same name but different arity (i.e. number of arguements, they are considered seperate functions).

So:

def func(a,b)  
IO.puts a
end

Is a different function to:

def func(a)  
IO.puts a
end

To that effect we are going to have two functions.

multiply/2 which is the one that is publicly exposed and consumed by other modules, and mulitply/3 which is called by the multiply/2function.

So basically we need first create a function which takes two numbers which are to be multiplied and call our second multiply/3 function passing in an accumulator. We will use the accumulator to track the end result from the function.

def multiply(n1,n2) do  
mutliply(n1,n2,0)
end

(We could even write this on a single line)

def multiply(n1,n2), do: multiply(n1,n2,0)

Now we need to actually implement the multiplier logic.

When dealing with recursion in elixir it is always best to write your success or end function head first, so that the function actually has an exit point (e.g. won’t run into infinity).

The way our recursive function is going to work is that we are going to add n1 to the accumulator (which starts at 0) for every value of n2 and subtract 1 from n2 until we reach 0.

So basically:

10 * 10 would look like:

From this, we can tell that our success or end case, is when n2 is equal to 0.

Therefore, the function will look like:

def multiply(n1,n2), do: multiply(n1,n2,0)
defp multiply(_n1, 0, acc), do: acc

(remember defp makes it a private method).

So here we are saying that if multiply/3 is called and the value of n2is equal to 0, then don't iterate again, instead just return the current value of the accumulator.

This is our end result. Now we need to implement the iteration logic.

Now remember we need to add the value of n1 to acc and subtract the value of n2 by 1.

That looks like this:

def multiply(n1,n2,acc) do  
new_acc = n1 + acc
new_n2 = n2 - 1
  #recursive call
multiply(n1, new_n2, new_acc)
end

That last line calls the same function again with the new values of n2and acc.

However, this looks pretty messy.. let’s refactor it a bit to look more proper.

def multiply(n1,n2,acc) do  
multiply(n1, n2 - 1, acc + n1)
end

We can even right this on a single line:

def multiply(n1,n2,acc), do: multiply(n1, n2 - 1, acc + n1)

And that’s it, we can now multiply two numbers together in just three lines of Elixir.

The final implementation looks like:

def multiply(n1,n2), do: multiply(n1,n2,0)  
defp multiply(_n1, 0, acc), do: acc
defp multiply(n1,n2,acc), do: multiply(n1, n2 - 1, acc + n1)

Pretty neat huh?

Now obviously this won’t handle negative numbers, but that’s pretty easy to handle as well.

Again, there is no need to use if statements here, instead we can use guard_clauses.

Guard clauses are essentially, parts of a function head that add conditions to the passed in arguments. It’s another way of pattern matching basically.

In our case, this be achieved by checking if the value of n2 is less then 0. If it is, we simply reverse the operations on n2 and acc (e.g. we add 1 to n2 and subtract n1 from acc).

This is what that head will look like:

def multiply(n1,n2,acc) when n2 < 0 do  
multiply(n1, n2 + 1, acc - n1)
end
# or on one line
def multiply(n1,n2,acc) when n2 < 0, do: multiply(n1, n2 + 1, acc - n1)

That when n2 < 0 part is the guard clause. We are saying here that first only call this function head if the arguments can be matched to n1,n2,acc (which they can) AND if n2 is less then 0.

Now because this is recursive, functions in Elixir are checked in the order that they are defined. So e.g. if we had this method below our original one, it would never get called:

def multiply(n1,n2), do: multiply(n1,n2,0) # 1
  defp multiply(_n1,0,acc), do: acc # 2
defp multiply(n1,n2,acc), do: multiply(n1,n2 - 1, acc + n1) #3
defp multiply(n1,n2,acc) when n2 < 0, do: multiply(n1,n2 + 1, acc - n1) #4 - Never called

This is because function head #3 will always match the arguments (assuming it passes through function head #2). Therefore, all we need to do is move #4 above #3 e.g.

def multiply(n1,n2), do: multiply(n1,n2,0) 
  defp multiply(_n1,0,acc), do: acc
defp multiply(n1,n2,acc) when n2 < 0, do: multiply(n1,n2 + 1, acc - n1)
defp multiply(n1,n2,acc), do: multiply(n1,n2 - 1, acc + n1)

Now we have a fully working mutliply function written from scratch, using pattern matching and recursion.

Below is some sample output(note the method was defined under a module called Recurse:

iex(1)> Recurse.multiply(2,-3)  
#=> -6
iex(2)> Recurse.multiply(-2,-3)
#=> 6
iex(3)> Recurse.multiply(2, 3)
#=> 6
iex(4)> Recurse.multiply(-2, 3)
#=> -6

If you have enjoyed this little guide or have any questions, let me know in the comments below. I’d be happy to help you out!

Hacker Noon is how hackers start their afternoons. We’re a part of the @AMIfamily. We are now accepting submissions and happy to discuss advertising &sponsorship opportunities.
To learn more, read our about page, like/message us on Facebook, or simply, tweet/DM @HackerNoon.
If you enjoyed this story, we recommend reading our latest tech stories and trending tech stories. Until next time, don’t take the realities of the world for granted!
Topics of interest

More Related Stories