Loops in Elixir

July 11, 2020 8-minute read

Introduction

In the following post we will look at a few ways to interate over the first one hundred integers (0 through 99) in Elixir calling FizzBuzz on each.

Elixir lacks the familiar for, while, until language control-flow constructs that exist in other languages, instead encouraging use of the enumeration capabilities available in the collection modules within the Elixir standard library.

The core requirements of a FizzBuzz, when passed an integer as a parameter, is to;

Return the string "FizzBuzz" when that integer divided by both three and five has a remainder of zero,
Return the string "Fizz" when that integer has a remainder of zero when divided by three,
Return the string "Buzz" when that integer has a remainder of zero when divided by five,
Otherwise, return the integer

This implementation will return the results as a list instead of simply printing to standard out.

FizzBuzz in Elixir

Implementing FizzBuzz in idiomatic Elixir is to use the pattern matching capabilities ^[1] inherent to the language.

In the following example, we do away with the switch/if/else language constructs by using a combination of anonymous function and pattern matching.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def fb(n) do
  f = fn
    0, 0, _ -> "FizzBuzz" (2)
    0, _, _ -> "Fizz" (3)
    _, 0, _ -> "Buzz" (4)
    _, _, n -> n (5)
  end

  f.(rem(n, 3), rem(n, 5), n) (1)
end

1	In the body of `fb` we call an anonymous function that accepts three arguments, passing the remainder of `n % 3`, `n % 5`, and `n` respectively.
2	This clause matches when both `n % 3` and `n % 5` return zero. `_` means that we don’t care about that parameter.
3	This clause matches when only `n % 3` returns zero.
4	This clause matches when only `n % 5` returns zero.
5	This final clause matches when neither `n % 3` or `n % 5` return zero.

The following example uses named functions to similar effect.

1
2
3
4
5
def fb(0, 0, _), do: "FizzBuzz"
def fb(0, _, _), do: "Fizz"
def fb(_, 0, _), do: "Buzz"
def fb(_, _, n), do: n
def fb(n), do: fb(rem(n, 3), rem(n, 5), n)

Of course, it is possible to write C in any language as shown in the following example.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def fb(n) do
  cond do
    rem(n, 3) == 0 and rem(n, 5) == 0 ->
      "Fizzbuzz"

    rem(n, 3) == 0 ->
      "Fizz"

    rem(n, 5) == 0 ->
      "Buzz"

    n ->
      n
  end
end

Looping using `Enum.map`

We can use Enum.map to return a new collection containing the results of invoking our fb function 100 times. The number of times we wish to iterate on the FizzBuzz function we define as a range 0..n, and pass this range to Enum.map as the first parameter. Enum.map calls our fb function on each item in range.

In Elixir, a range is stored as a struct (start and end values) and is not expanded into, in our example, a collection of 100 individual integers. So using a range is space efficient.

1
2
3
def fizzbuzz(n) do
  Enum.map(0..n, &fb/1)
end

Looping using Pipes

Rewriting our fizzbuzz function to use a pipe (|>) may be easier to read. The range is "piped" into Enum.map as the first parameter.

1
2
3
4
def fizzbuzz(n) do
  0..n
  |> Enum.map(&fb/1)
end

Looping using the `for` special form

The for special form iterates over each item in a collection (the range 0..n in our example), and assigns each item to num, which is then passed to fb in the body of the for.

1
2
3
def fizzbuzz(n) do
  for num <- 0..n, do: fb(num)
end

Attentive readers may have noticed that in the Introduction I mentioned that Elixir does not have a for looping construct, and yet, here it is. The mechanics of for in Elixir are quite different than what you may be used to coming from other languages, even though in this contrived example the results are the same. In Elixir the thing on the left of the ← is pattern matched to the item in the collection on the right. Whereas in languages like Golang, a variable is assigned the value.

1
2
3
for i := 0; i < n; i++ {
    fb(i)
}

Recursion

An initial recursive algorithm to calculate FizzBuzz for the first 100 integers is defined below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def fizzbuzz_helper(0, _) do (1)
  [fb(0)]
end

def fizzbuzz_helper(n, list) do
  [fb(n) | fizzbuzz_helper(n - 1, list)] (2)
end

def fizzbuzz(n) do
  fizzbuzz_helper(n, [])
  |> Enum.reverse() (3)
end

1	Our base case that terminates recursion.
2	Prepend to the collection as the stack is unwound.
3	Reverse the collection so items are in ascending order.

This algorithm is correct but it is very inefficient. Our algorithm is O(3N), at least three times slower than Enum.map:

O(N) to iterate to the base case,
O(N) to unwind the stack, creating the collection as we go,
O(N) to reverse the collection.

For starters, we need to reverse the collection to return the items in ascending order which is a O(N) operation. We add new items to the front of a list and reverse the list as the last operation as this more efficient that adding items to the end of the list. Pre-pending an item to a list is always a O(1) cost, while appending an item is O(N) which would make our algorithm O(N^2) — polynomial time. Much, much slower than O(3N).

Computational complexity is O(N^2) as we will have to traverse the collection each time to add an item to the end, which has O(N) cost, in each call to fb, which itself is called N times (except the last). So O(N x N) is O(N^2).

Tail Recursion

But even worse, we have not implemented our algorithm in a way that is Tail Recursive.^[2] The compiler must build a chain of stack frames on successive recursive calls containing the deferred operations ^[3] that will prepend the result of fb to the collection returned by fizzbuzz_helper, shown here [fb(n) | fizzbuzz_helper(n - 1, list)].

And not being Tail Recursive means that a large enough loop will overflow the stack and cause a runtime error. The BEAM virtual machine must allocate memory for each stack frame created, and if the number of recursion calls is too great, eventually the pool of memory allocated to the stack will be exhausted.

Lisps generally support tail call optimization.^[4]. Racket and the Schemes, Common Lisp (most implementations), and Elixir all do. Clojure does not (a limitation of the JVM), and thus requires use of the Trampoline pattern.^[5]. When recursion is implemented as a tail call — in other words, the recursive call is performed as the very last action in the function — the compiler is able to transform the recursive procedure into an iterative process (a GOTO). No stack frames are created and thus there is no danger of blowing the stack even for a very large number of iterations. In effect, recursion becomes as efficient as a for loop.

In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written.

— SICP (Structure and Interpretation of Computer Programs)

The changes in the following example allow for tail call optimization. We add the item to the collection before re-cursing, not after. An additional benefit, we no longer need to reverse the collection as items are added to the collection in ascending order.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def fizzbuzz_helper(0, list) do
  [fb(0) | list]
end

def fizzbuzz_helper(n, list) do
  fizzbuzz_helper(n - 1, [fb(n) | list]) (1)
end

def fizzbuzz(n) do
  fizzbuzz_helper(n, [])
end

1	The result of `fb` is added to the list before recursion.

With these changes our algorithm becomes O(N).

In Conclusion

Use the capabilities of the standard library unless precluded by the use case. Otherwise for anyone reading your code, valuable thought cycles will be lost trying to understand why the wheel needed to be re-implemented.
Try to implement any recursive procedure in a way that is Tail recursive to allow the compiler to change this to an iterative process.

Tail recursion is not required for algorithms having a low computation complexity cost, for example calculating GCD recursively is N(log N), where the problem space is halved on each pass.

1
2
3
4
defmodule Gcd do
  def gcd(a, 0), do: a
  def gcd(a, b), do: gcd(b, rem(a, b))
end

1. https://hexdocs.pm/elixir/patterns-and-guards.html

2. https://en.wikipedia.org/wiki/Tail_call

3. https://mitpress.mit.edu/sites/default/files/sicp/full-text/sicp/book/node15.html

4. https://en.wikipedia.org/wiki/Tail_call

5. https://clojuredocs.org/clojure.core/trampoline