The Inquisitive Developer

Learn With Me: Elixir - FizzBuzz (#30)

Kevin Peter -

It's always good to take the occasional pause and practice what we've learned, so today I'm going do some Elixir practice by implementing FizzBuzz in Elixir. For those of you who are unfamiliar with FizzBuzz, it's a simple programming exercise that's often used to assert a very basic ability to program.

The rules of FizzBuzz go like this. We start at 1 and count up to N, where N can be any positive integer. As we count, we output "fizz" when the number is divisible by 3, "buzz" when the number is divisible by 5, and "fizzbuzz" when the number is divisible by 3 and 5. If the number does not meet any of these criteria, we just output the number.

That's pretty easy and typically involves modulo operations to determine whether a number is divisible by another number, in which case the remainder is 0. It's a perfect exercise for practicing our Elixir skills.

If you're interested in trying this out for yourself, I encourange you to implement FizzBuzz on your own before continuing to read about my solution.

The Strategy

The plan is to decouple the FizzBuzz calculation from the side effects, which is a functional way to do things. So I'm going to compute the FizzBuzz results, store them in a list, and then pass that list to a separate function whose purpose is to output that list by displaying each element on the screen.

The Recursive Implementation

I'm going to start out with an implementation of FizzBuzz using a recursive function implementation. That will get me some more practice using recursion and pattern matching in Elixir.

The module is called FizzBuzz and it implements a count/1 function. The count/1 function takes a count and returns a list containing the FizzBuzz output for that count. Here's what count/1 looks like.

#The base case: gets called when count is 0
defp count(0) do
	[]
end

#Gets called when the count is divisible by 3 and 5
defp count(count) when rem(count, 3) == 0 and rem(count, 5) == 0 do
	["fizzbuzz" | count(count - 1)]
end

#Gets called when the count is divisible by 3
defp count(count) when rem(count, 3) == 0 do
	["fizz" | count(count - 1)]
end

#Gets called when the count is divisible by 5
defp count(count) when rem(count, 5) == 0 do
	["buzz" | count(count - 1)]
end

#Gets called when the count is not divisible by 3 or 5
defp count(count) do
	[Integer.to_string(count) | count(count - 1)]
end

These are all function clauses of the same function, count/1.

  1. The first clause serves as the base case. When the count is 0, it returns an empty list. There's nothing to output when the list is empty.
  2. The second clause is called when the count is divisible by 3 and divisible by 5. We use pattern matching via guard clauses to ensure that this function clause is only called under these conditions. It returns "fizzbuzz" and the tail of the list is filled in by a recursive call after the count parameter has been decremented. I found when implementing this clause that I had to place it above the others because it is the most specific clause. If I put it below the other clauses, it would never get called because those clauses are more generic and would match first.
  3. The third clause is called when the count is divisible by 3. We know it's not also divisible by 5 because the above clause would have already matched in that case. We return "fizz" as the head of the list and do a recursive call to fill in the tail of the list.
  4. The fourth clause is called when the count is divisible by 5. We know it's not divisible by 3 because an earlier clause would have already matched in that case. We return "buzz" as the head of the list and do a recursive call to fill in the tail of the list.
  5. Finally we get to the most generic clause. If there was no match for the clauses above, then the count parameter is neither divisible by 3 nor by 5. So in this case, we convert the integer to a string for the head of the list and make a recursive call to fill in the tail of the list.

Great, we now have a nice recursive function that computes the FizzBuzz values for us. Next I'm going to implement the function that prints out those values.

I'm also going to make this a recursive function as well.

#Base case: prints out an empty list
defp print([]) do
end

#Prints out the contents of a list
defp print([head | tail]) do
	IO.puts(head)
	
	print(tail)
end

That's pretty simple. It prints out the head of the list and then calls itself to print out the tail of the list. Eventually, it will match the base case and complete. This particular function, by the way, is tail call optimized because the last thing it does is call itself.

Now we need a function to combine count/1 with print/1.

def perform_count(total_count)) when total_count >= 0 do
	total_count
	|> count()
	|> Enum.reverse()
	|> print()
end

This function represents the module's public interface, and composes the module's private functions using a pipeline to do the work of FizzBuzz. The total_count parameter starts off the pipeline. It's passed to the count/1 function and returns a list of FizzBuzz values. That list was constructed in reverse order, so it needs to be passed to Enum.reverse/1 to be put into the correct order. Finally, the list is passed to the print/1 function to be output to the screen.

I had to add a guard clause to restrict the parameter to non-negative numbers. Otherwise, a call with a negative number results in infinite recursion because the parameter value is always decremented, and would never reach the base case.

You can find the recursive implementation in the FizzBuzz folder under the projects folder in the Learn With Me: Elixir repository on Github. It's in the "fizzbuzz_recursive.exs" file.

During development, I made the private functions temporarily public and tested them manually (no automated unit tests yet), so I was fairly confident it would work when I composed them. It did. Here are some examples of the output.

iex> FizzBuzz.perform_count(5)
1
2
fizz
4
buzz
nil
iex> FizzBuzz.perform_count(1)
1
nil
iex> FizzBuzz.perform_count(0)
nil
iex> FizzBuzz.perform_count(-1)
** (FunctionClauseError) no function clause matching in FizzBuzz.perform_count/1

    The following arguments were given to FizzBuzz.perform_count/1:

        # 1
        -1

    projects/FizzBuzz/fizzbuzz_recursive.exs:2: FizzBuzz.perform_count/1
iex> FizzBuzz.perform_count(20)
1
2
fizz
4
buzz
fizz
7
8
fizz
buzz
11
fizz
13
14
fizzbuzz
16
17
fizz
19
buzz
nil

The nil value is what the perform_count/1 function returns because the last expression was a side effect, and did not attempt to return anything useful. It just printed everything out to the screen instead.

The Tail Call Optimized Implementation

So now I have a working FizzBuzz implementation. Yay! That wasn't terribly difficult, but it was fun to be able to apply what I've learned so far and build something on my own. Now I'm going to improve upon that and implement FizzBuzz using recursion with tail call optimization. We'll be able to FizzBuzz into the billions without worrying about call stack memory usage.

Let's look at the count function with tail call optimization. This function is now count/2 because we added an extra parameter to keep track of the current FizzBuzz output.

#The base case: gets called when count is 0
defp count(0, output) do
	output
end

#Gets called when the count is divisible by 3 and 5
defp count(count, output) when rem(count, 3) == 0 and rem(count, 5) == 0 do
	count(count - 1, ["fizzbuzz" | output])
end

#Gets called when the count is divisible by 3
defp count(count, output) when rem(count, 3) == 0 do
	count(count - 1, ["fizz" | output])
end

#Gets called when the count is divisible by 5
defp count(count, output) when rem(count, 5) == 0 do
	count(count - 1, ["buzz" | output])
end

#Gets called when the count is not divisible by 3 or 5
defp count(count, output) do
	count(count - 1, [Integer.to_string(count) | output])
end

Instead of the output being returned from the recursive call and then modified, it's modified first and then passed to the next recursive call. We are using the prepend operation, which is the most efficient method of constructing a list. That plus the fact that we are starting at the highest number and decrementing for each recursive call means that the FizzBuzz output is prepended in the correct order and doesn't need to be reversed at the end. The previous example without tail call optimization returned the output in reverse order and had to be reversed.

Since the recursive call is the very last thing the recursive function clauses do, Elixir will optimize it with tail call optimization.

The perform_count/1 method is slightly different because it has to pass in the initial output (an empty list) to the new count/2 function as well as the count coming from the previous step in the pipeline.

def perform_count(total_count) do
	total_count
	|> count([])
	|> print()
end

You can find the tail-call-optimized implementation in the FizzBuzz folder under the projects folder in the Learn With Me: Elixir repository on Github. It's in the "fizzbuzz_recursive_optimized.exs" file.

I tried running this with a count of 1 million and it succeeded after several minutes of running. The I/O is almost certainly the bottleneck here, as it usually is with these sorts of things. The memory usage of the Erlang VM process stayed within the 50-60MB range the entire time, which is about the same as when IEx is idling waiting for input. So running it with a count of 1 billion would be doable, but would take many hours.

So to see how well it performed without I/O, I commented out the call to the print/1 function, so that the function returns the list instead of writing it to the screen. A count of 1 million took less than a second. I tried running it with a count of 1 billion, but after 5 minutes and 30GB of memory usage, I decided to terminate the process. The memory usage wasn't coming from a call stack, but from the enormous list of FizzBuzz output that it was constructing. A billion elements is a lot of elements to store in a list, and that uses a lot of memory.

The Enum Implementation

Writing recursive code is not the only way to solve FizzBuzz in Elixir. The Enum module also offers some interesting functions we can use. I identified the Enum.map/2 function as the perfect function to use. It can map a range of integers to a list of FizzBuzz output. Enum.map/2 almost certainly uses recursion internally, but that's not something we have to think about.

So here's the implementation I came up with.

#Maps an integer range to FizzBuzz output
defp count(count) do
	Enum.map(1..count, &number_to_fizzbuzz/1)
end

#Gets called when the number is divisible by 3 and 5
defp number_to_fizzbuzz(number) when rem(number, 3) == 0 and rem(number, 5) == 0 do
	"fizzbuzz"
end

#Gets called when the number is divisible by 3
defp number_to_fizzbuzz(number) when rem(number, 3) == 0 do
	"fizz"
end

#Gets called when the number is divisible by 5
defp number_to_fizzbuzz(number) when rem(number, 5) == 0 do
	"buzz"
end

#Gets called when the number is not divisible by 3 or 5
defp number_to_fizzbuzz(number) do
	Integer.to_string(number)
end

The count/1 method just maps a range of integers to the corresponding FizzBuzz output, with the number_to_fizzbuzz/1 function doing the work of mapping a single number to a single FizzBuzz output. Now that I'm looking at this code again, I suspect that it doesn't handle 0 properly, so I'd probably have to add a clause to handle 0.

All the perform_count/1 function does in this example is call count/1 and passes the result to print/1.

You can find the Enum implementation in the FizzBuzz folder under the projects folder in the Learn With Me: Elixir repository on Github. It's in the "fizzbuzz_enum.exs" file

This is the version of FizzBuzz I like the most because it's the most easily readable version. It's also the most compact version. That helps show the power of the layer of abstraction that reusable functions in the Enum module provide by implementing common customizable (via the function passed in as the second parameter) recursive algorithms for us. It simplifies our code. I love higher-order functions!

I'm pretty happy with how my FizzBuzz code turned out. It got me some good practice using Elixir and was a fun little problem to solve.