Introducing Elixir: Getting Started in Functional Programming (2014)

Chapter 4. Logic and Recursion

So far, Elixir seems logical but fairly simple. Pattern matching controls the flow through a program, and requests that match a form return certain responses. While this is enough to get many things done, there are times when you’ll want more powerful options, especially as you start working with larger and more complicated data structures.

Logic Inside of Functions

Pattern matching and guards are powerful tools, but there are times when it’s much easier to do some comparisons inside of a function clause instead of creating new functions. Elixir’s designers agreed and created two constructs for evaluating conditions inside of functions: the caseexpression and the less frequently used cond and if expressions.

The case construct lets you use pattern matching and guards inside of a function clause. It reads most clearly when a single value (or set of values) needs to be compared with multiple possibilities. The cond construct evaluates only a series of guards, without pattern matching. The condconstruct tends to produce more readable code in situations where the multiple possibilities are specified by combinations of different values. The if construct evaluates only a single guard.

All these constructs return a value your code can capture.

Evaluating Cases

The case construct lets you perform pattern matching inside of your function clause. If you found the multiple function clauses of Example 3-2 hard to read, you might prefer to create a version that looks like Example 4-1, which you can find in ch04/ex1-case.

Example 4-1. Moving pattern matching inside the function with case

defmodule Drop do

def fall_velocity(planemo, distance) whendistance >= 0 do

case planemo do

:earth -> :math.sqrt(2 * 9.8 * distance)

:moon -> :math.sqrt(2 * 1.6 * distance)

:mars -> :math.sqrt(2 * 3.71 * distance)

end

The case construct will compare the atom in planemo to the values listed, going down the list in order. It won’t process beyond the match it finds. Each matching value is followed by a ->, which you can read as “yields”. The case construct will return the result of different calculations based on which atom is used, and because the case construct returns the last value in the function clause, the function will return that value as well.

NOTE

You can use the underscore (_) for your pattern match if you want a choice that matches “everything else.” However, you should always put that last — nothing that comes after that will ever be evaluated.

The results should look familiar:

iex(1)> c("drop.ex")

[Drop]

iex(2)> Drop.fall_velocity(:earth,20)

19.79898987322333

iex(3)> Drop.fall_velocity(:moon,20)

8.0

iex(4)> Drop.fall_velocity(:mars,-20)

** (FunctionClauseError) no function clause matching: Drop.fall_velocity(:mars, -20)

drop.ex:3: Drop.fall_velocity(:moon, -20)

The case construct switches among planemos, while the guard clause on the function definition keeps out negative distances, producing (rightly) the error on line 4. This way the guard needs to appear only once.

You can also use the return value from the case construct to reduce duplicate code and make the logic of your program clearer. In this case, the only difference between the calculations for earth, moon, and mars is a gravitational constant. Example 4-2, which you can find in ch04/ex2-case, shows how to make the case construct return the gravitational constant for use in a single calculation at the end.

Example 4-2. Using the return value of the case construct to clean up the function

defmodule Drop do

def fall_velocity(planemo, distance) whendistance >= 0 do

gravity = case planemo do

:earth -> 9.8

:moon -> 1.6

:mars -> 3.71

end

:math.sqrt(2 * gravity * distance)

end

This time, the gravity variable is set to the return value of the case construct. The now more readable formula math:sqrt(2 * gravity * distance) is the last line of the function, and the value it produces will be the return value.

You can also use guards with a case statement, as shown, perhaps less than elegantly, in Example 4-3, which is in ch04/ex3-case. This might make more sense if there were different planemos with different rules about distances.

Example 4-3. Moving guards into the case statement

defmodule Drop do

def fall_velocity(planemo, distance) do

gravity = case planemo do

:earth whendistance >= 0 -> 9.8

:moon whendistance >= 0 -> 1.6

:mars whendistance >= 0 -> 3.71

end

:math.sqrt(2 * gravity * distance)

end

This produces similar results, except that the error message at the end changes from (FunctionClauseError) no function clause matching: Drop.fall_velocity(:mars, -20) to (CaseClauseError) no case clause matching: :mars:

iex(7)> c("drop.ex")

[Drop]

iex(8)> Drop.fall_velocity(:earth,20)

19.79898987322333

iex(9)> Drop.fall_velocity(:moon,20)

8.0

iex(10)> Drop.fall_velocity(:mars,-20)

** (CaseClauseError) no case clause matching: :mars

drop.ex:4: Drop.fall_velocity/2

The error is correct, in that the case construct is trying to match :mars, but misleading because the problem isn’t with :mars but rather with the guard that’s checking the distance variable. If Elixir tells you that your case doesn’t match but a match is obviously right there in front of you, check your guard statements.

Adjusting to Conditions

The cond construct is broadly similar to the case statement, but without the pattern matching. If you would like, this allows you to write a catch-all clause — a guard matching true at the end. This often makes it easier to express logic based on broader comparisons than simple matching.

Suppose, for example, that the precision of the fall_velocity function is too much. Instead of an actual speed, you’d like to describe the speed produced by dropping from a tower of a given height. You can add a cond construct that does that to the earlier code from Example 4-2, as shown in Example 4-4, in ch04/ex4-cond.

Example 4-4. Adding an if construct to convert numbers into atoms

defmodule Drop do

def fall_velocity(planemo, distance) whendistance >= 0 do

gravity = case planemo do

:earth -> 9.8

:moon -> 1.6

:mars -> 3.71

end

velocity = :math.sqrt(2 * gravity * distance)

conddo

velocity == 0 -> :stable

velocity < 5 -> :slow

velocity >= 5 andvelocity < 10 -> :moving

velocity >= 10 andvelocity < 20 -> :fast

velocity >= 20 -> :speedy

end

This time, the cond construct returns a value (an atom describing the velocity) based on the many guards it includes. Because that value is the last thing returned within the function, that becomes the return value of the function.

The results are a little different from past trials:

iex(1)> c("drop.ex")

[Drop]

iex(2)> Drop.fall_velocity(:earth,20)

:fast

iex(3)> Drop.fall_velocity(:moon,20)

:moving

iex(4)> Drop.fall_velocity(:mars,20)

:fast

iex(5)> Drop.fall_velocity(:earth,30)

:speedy

If you want to capture the value produced by the cond construct in a variable, you can. Just replace the cond do in the first line with something like description = cond do.

NOTE

Elixir evaluates the cond and if statements on the basis of truthiness. All values are considered to be true except nil and false.

If, or else

For simpler cases, Elixir also offers an if function that tests only a single clause, and allows an else to follow if a failed test also requires action.

Example 4-5, in ch04/ex5-if, sends a warning to standard output (in this case IEx) if you drop an object too fast. It uses the simpler cousin of cond, if, to decide whether to put out the extra message.

Example 4-5. Sending an extra warning if the velocity is too high

defmodule Drop do

def fall_velocity(planemo, distance) whendistance >= 0 do

gravity = case planemo do

:earth -> 9.8

:moon -> 1.6

:mars -> 3.71

end

velocity = :math.sqrt(2 * gravity * distance)

if velocity > 20 do

IO.puts("Look out below!")

else

IO.puts("Reasonable...")

end

velocity

end

The new if clause checks the velocity variable to see if it’s above 20. If it is, it calls IO.puts, which creates a side effect: a message on the screen. If not, the else clause puts a milder message on the screen. (The velocity at the end makes sure that the calculated result is the return value.):

iex(1)> c("drop.ex")

[Drop]

iex(2)> Drop.fall_velocity(:earth,50)

Look out below!

31.304951684997057

iex(3)> Drop.fall_velocity(:moon,100)

Reasonable...

17.88854381999832

You can write if statements in a few different ways. The if statement is compact enough that it can be tempting to put it on a single line:

iex(4)> x=20

iex(5)> if x>10 do :large end

:large

That worked well, and you can even add an else:

iex(6)>if x>10 do :large else :small end

:large

As an alternative, Elixir lets you put a colon after the do and then use a shorter form:

iex(6)> if x>10, do: :large, else: :small

:large

You may also find Elixir’s unless statement more readable than an if when you want to test against an opposite:

iex(8)> unless x>10, do: :small, else: :large

:large

Variable Assignment in case and if Constructs

Every possible path created in a case, cond, or if statement has the opportunity to bind values to variables. This is usually a wonderful thing, but could let you create unstable programs by assigning different variables in different clauses. This might look something like Example 4-6, which you can find in ch04/ex6-broken.

Example 4-6. A badly broken cond construct

defmodule Broken do

def bad_cond(test_val) do

conddo

test_val < 0 -> x=1

test_val >= 0 -> y=2

end

x+y

end

Erlang would have stopped you from doing this by refusing to compile the code and letting you know that there are unsafe variables. Elixir, however, lets it compile, and then breaks at runtime:

iex(1)> c("broken.ex")

[Broken]

iex(2)> Broken.bad_cond(20)

** (ArithmeticError) bad argument in arithmetic expression

broken.ex:10: Broken.bad_cond/1

NOTE

Elixir also lifts Erlang’s tight rules on what can happen in the clause being evaluated by if and cond. Erlang only lets you use the features available in guards, ensuring that there will be no side effects. Elixir doesn’t have those limits.

The Gentlest Side Effect: IO.puts

Up until Example 4-5, all of the Elixir examples you’ve seen focused on a single path through a group of functions. You put an argument or arguments in, and got a return value back. That approach is the cleanest way to do things: you can count on things that worked before to work again because there’s no opportunity to muck up the system with leftovers of past processing.

Example 4-5 stepped outside of that model, creating a side effect that will linger after the function is complete. The side effect is just a message that appears in the shell (or in standard output when you start running Elixir outside of the shell). Applications that share information with multiple users or keep information around for longer than a brief processing cycle will need stronger side effects, like storing information in databases.

Elixir best practice suggests using side effects only when you really need to. An application that presents an interface to a database, for example, really will need to read and write that database. An application that interacts with users will need to put information on the screen (or other interface) so that users can figure out what they’re expected to do.

Side effects are also extremely useful for tracing logic when you are first starting out. The simplest way to see what a program is doing, before you’ve learned how to use the built-in tracing and debugging tools for processes, is to have the program report its status at points you consider interesting. This is not a feature you want to leave in shipping code, but when you’re getting started, it can give you an easily understandable window into your code’s behavior.

The IO.puts function lets you send information to the console, or, when you’re eventually running code outside of the console, to other places. For now, you’ll just use it to send messages from the program to the console. Example 4-5 showed the simplest way to use IO.puts, just printing a message it takes in double quotes:

IO.puts("Look out below!")

IO.puts adds a newline to the end, telling the console to start any new messages it sends at the beginning of the next line. It makes your results look a bit neater. If you don’t want a newline, you can use IO.write instead. If you want to print a variable that isn’t a string, you can useIO.inspect.

NOTE

Elixir flatly prohibits operations that could cause side effects in guard expressions. If side effects were allowed in guards, then any time a guard expression was evaluated — whether it returned true or false — the side effect would happen. IO.puts wouldn’t likely do anything terrible, but these rules mean that it too is blocked from use in guard expressions.

Simple Recursion

The main tool you’ll use to repeat actions is recursion: having a function call itself until it’s (hopefully) reached a conclusion. This can sound complicated, but it doesn’t have to be.

There are two basic kinds of useful recursion. In some situations, you can count on the recursion to reach a natural end. The process runs out of items to work on or reaches a natural limit. In other situations, there is no natural end, and you need to keep track of the result so the process will end. If you can master these two basic forms, you’ll be able to create many more complex variations.

NOTE

There is a third form, in which the recursive calls never reach an end. This is called an infinite loop and is best known as an error you’ll want to avoid. As you’ll see in Chapter 9, though, even infinite loops can be useful.

Counting Down

The simplest model of recursion with a natural limit is a countdown, like the one used for rockets. You start with a large number and count down to zero. When you reach zero, you’re done (and the rocket takes off, if there is one).

To implement this in Elixir, you’ll pass a starting number to an Elixir function. If the number is greater than zero, it will then announce the number and call itself with the number minus one as the argument. If the number is zero (or less), it will announce blastoff! and end. Example 4-7, found in ch04/ex7-countdown, shows one way to do this.

Example 4-7. Counting down

defmodule Count do

def countdown(from) whenfrom > 0 do

IO.inspect(from)

countdown(from-1)

end

def countdown(from) do

IO.puts("blastoff!")

end

The last clause could have a guard — when from <= 0 — but it would be useful only to make clear when the blastoff happens to human readers. Unnecessary guard clauses may lead to later confusion, so brevity is probably the best option here. However, you’ll get a warning that from is unused in the final clause. Here’s a test run:

iex(1)> c("count.ex")

count.ex:8: variable from is unused

[Count]

iex(2)> Count.countdown(2)

blastoff!

:ok

The first time through, Elixir chose the first clause of countdown(from), passing it a value of 2. That clause printed 2, plus a newline, and then it called the countdown function again, passing it a value of 1. That triggered the first clause again. It printed 1, plus a newline, and then it called the countdown function again — this time passing it a value of 0.

The value of 0 triggered the second clause, which printed blastoff! and ended. After running three values through the same set of code, the function comes to a neat conclusion.

NOTE

You could also implement this conclusion with an if statement inside a single countdown(from) function clause. This is unusual in Elixir. I find guards more readable in these cases, but you may see things differently.

Counting Up

Counting up is trickier because there’s no natural endpoint, so you can’t model your code on Example 4-7. Instead, you can use an accumulator. An accumulator is an extra argument that keeps track of the current result of past work, passing it back into a recursive function. (You can have more than one accumulator argument if you need, though one is often sufficient.) Example 4-8, which you can find in ch04/ex8-countup, shows how to add a countup function to the count module, which lets Elixir count up to a number.

Example 4-8. Counting up

defmodule Count do

def countup(limit) do

countup(1,limit)

end

defp countup(count, limit) whencount <= limit do

IO.inspect(count)

countup(count+1, limit)

end

defp countup(count, limit) do

IO.puts("finished!")

end

It produces results like the following:

iex(1)> c("count.ex")

count.ex:12: variable count is unused

count.ex:12: variable limit is unused

[Count]

iex(2)> Count.countup(2)

finished!

:ok

The countup/2 function, which does most of the work, remains private, not exported. This isn’t mandatory; you might make it public if you wanted to support counting between arbitrary values, but it’s a common practice. Keeping the recursive internal functions private makes it less likely that someone will misuse them for purposes they’re not well-suited to. In this case, it doesn’t matter at all, but it can make a big difference in other more complex situations, especially when data is modified.

When you call countup/1, it calls countup/2 with an argument of 1 (for the current count) and the limit value you provided for the upper limit.

If the current count is less than or equal to the upper limit, the first clause of the countup/2 function reports the current count value with IO.puts. Then it calls itself again, increasing the count by one but leaving the limit alone.

If the current count is greater than the upper limit, it fails the guard on the first clause, so the second clause kicks in, reports "Finished.", and is done.

WARNING

The guards here are sufficient to avoid infinite loops. You can enter zero, negative numbers, or decimals as arguments to countup/1 and it will terminate neatly. You can get into serious trouble, however, if your termination test relies on == or === for comparison to a single value rather than >= or <= for comparison to a range.

Recursing with Return Values

The counting examples are simple — they demonstrate how recursion works, but just discard the return values. There are return values — the IO.puts calls return the atom :ok — but they aren’t of much use. More typically, a recursive function call will make use of the return value.

A classic recursive call calculates factorials. A factorial is the product of all positive integers equal to or less than the argument. The factorial of 1 is 1; 1 by itself yields 1. The factorial of 2 is 2; 2 × 1 yields 2. It starts to get interesting at 3, where 3 × 2 × 1 is 6. At 4, 4 × 3 × 2 × 1 is 24, and the results get rapidly larger with larger arguments.

There was a pattern to that, though. You can calculate any factorial by multiplying the integer by the factorial of one less. That makes it a perfect case for using recursion, using the results of smaller integers to calculate the larger ones. This approach is similar to the countdown logic, but instead of just counting, the program collects calculated results. That could look like Example 4-9, which you’ll find in ch04/ex9-factorial-down.

Example 4-9. A factorial written with the counting-down approach

defmodule Fact do

def factorial(n) when n > 1 do

n * factorial(n-1)

end

def factorial(n) when n<=1 do

end

The first clause of factorial uses the pattern previously described. The first clause, used for numbers above one, returns a value that is the number n times the factorial of the next integer down. The second clause returns the value 1 when it reaches 1. Using <= in that comparison, rather than ==, gives the function more resilience against non-integer or negative arguments, though the answers it returns aren’t quite right: factorials really only work for integers of 1 or higher. The results are as previously suggested:

iex(1)> c("fact.ex")

[Fact]

iex(2)> Fact.factorial(1)

iex(3)> Fact.factorial(3)

iex(4)> Fact.factorial(4)

iex(5)> Fact.factorial(40)

815915283247897734345611269596115894272000000000

This works, but it may not be clear why it works. Yes, the function counts down and collects the values, but if you want to see the mechanism, you need to add some IO.puts calls into the code, as shown in Example 4-10. (You can find this at ch04/ex10-factorial-down-instrumented.)

Example 4-10. Looking into the factorial recursion calls

defmodule Fact do

def factorial(n) whenn > 1 do

IO.puts("Calling from #{n}.")

result = n * factorial(n-1)

IO.puts("#{n} yields #{result}.")

result

end

def factorial(n) whenn<=1 do

IO.puts("Calling from 1.")

IO.puts("1 yields 1.")

end

There’s a bit more overhead here. To present the result of the recursive call and still return that value to the next recursive call requires storing it in a variable, here called result. The IO.puts call makes visible which value produced the result. Then, because the last value expression in a function clause is the return value, result appears again. The second clause for 1 is similar, except that it can report simply that 1 yields 1. because it always will.

When you compile this and run it, you’ll see something like the following:

iex(1)> c("fact.ex")

[Fact]

iex(2)> Fact.factorial(4)

Calling from 4.

Calling from 3.

Calling from 2.

Calling from 1.

1 yields 1.

2 yields 2.

3 yields 6.

4 yields 24.

Although the calls count down the values, as the logic would suggest, the messages about results don’t appear until the countdown is complete, and then they all appear in order, counting up.

The reason this happens is that the function calls don’t return values until the countdown is complete. Until then, Elixir builds a stack of frames corresponding to the function calls. You can think of the frames as paused versions of the function logic, waiting for an answer to come back. Once the call with an argument of 1 returns a simple value, not calling any further, Elixir can unwind those frames and calculate the result. That unwinding presents the results — “X yields Y” — in the order that the frames unwind.

That “unwinding” also means that the code in Example 4-9 and Example 4-10 is not tail recursive. When Elixir encounters code that ends with a simple recursive call, it can optimize the handling to avoid keeping that stack of calls around. This probably doesn’t matter for a one-time calculation, but it makes a huge difference when you write code that will stay running for a long time.

You can achieve tail recursion for factorials by applying the counting-up approach to factorials. You’ll get the same results (at least for integer values), but the calculations will work a little differently, as shown in Example 4-11, at ch04/ex11-factorial-up.

Example 4-11. A factorial written with the counting-up approach

defmodule Fact do

def factorial(n) do

factorial(1,n,1)

end

defp factorial(current, n, result) whencurrent <= n do

new_result = result * current

IO.puts("#{current} yields #{new_result}.")

factorial(current+1, n, new_result)

end

defp factorial(_current, _n, result) do

IO.puts("finished!")

result

end

As in the counting-up example, the main function call, here factorial/1, calls a private function, factorial/3. In this case, there are two accumulators. current stores the current position in the count, whereas result is the answer from the previous multiplication. When the value ofcurrent climbs past the limiting value n, the first guard fails, the second clause is invoked, and the function is finished and returns the result. (You’ll get a compilation warning because the final clause doesn’t use the accumulator variables current or n. You can ignore it.)

Because factorial/3’s last call in the recursive section is to itself, without any complications to track, it is tail recursive. Elixir can minimize the amount of information it has to keep around while the calls all happen.

The calculation produces the same results, but does the math in a different order:

iex(1)> c("fact.ex")

[Fact]

iex(2)> Fact.factorial(4)

1 yields 1.

2 yields 2.

3 yields 6.

4 yields 24.

finished!

Although the code is tracking more values, the runtime has less to do. When it finally hits the final result, there’s no further calculation needed. That result is the result, and it passes back through to the original call. This also makes it easier to structure the IO.puts calls. If you remove them or comment them out, the rest of the code stays the same.