Archive for October, 2014

Fizz Buzz with Functional Programming

Saturday, October 11th, 2014

Fizz Buzz is a counting game where players count upwards saying either the number, “Fizz!” if the number is a multiple of 3, “Buzz!” if a multiple of 5, or “Fizz! Buzz!” if the a multiple of 3 and 5.

It’s also a simple programming problem that can be solved in a number of ways.

In C#, the solution could be as simple as:

var max = 30;
 
Console.WriteLine("With a for loop:");
 
for (var i = 1; i <= max; i++)
{
    Console.Write(i + ": ");
 
    if (i % 3 == 0)
    {
        Console.Write("Fizz! ");
    }
 
    if (i % 5 == 0)
    {
        Console.Write("Bang!");
    }
 
    Console.WriteLine();
}

href=”https://github.com/robert-impey/CodingExperiments/blob/master/C-Sharp/FizzBang/FizzBang/Program.cs

I’m going to show a way of solving this problem using F#. This is not the simplest way to solve this problem. However, the F# solution below does demonstrate the use of higher order functions, an important concept in functional programming.

F# is a strongly typed language. This means that the compiler checks that the values that we bind and pass to and return from functions conform to its expectations. This catches a huge number of programmer errors almost as soon as they are made. It also allow the programmer to state his or her intentions by defining types. In this program, we are dealing with checking numbers that may or may not have the special property of causing us to say a message. We are going to need a function that can check numbers, so we define a type that describes such functions:

type NumberChecker = int -> string option

An example of such a function is

let isEven x = 
    if x % 2 = 0 then Some "That number's even!"
    else None

This takes x and checks whether the remainder after dividing by 2 is 0. If so, it returns something (the message). Otherwise, it returns nothing.

We can test this function using a match statement. We call isEven with a number. If the function returns a message (the case where there is Some message) we can print it. If the function returned None, then we’ll just print the number.

let number = 4
match isEven number with
| Some message -> printfn "%s" message
| None -> printfn "%d" number

This code is fine if we only want to check one number with one number checker. We want to be able to check numbers with different checker functions.

For example, we might also define:

let isOdd x =
    if x % 2 = 1 then Some "That number's odd!"
    else None

To test this, we could duplicate our code:

match isOdd number with
| Some message -> printfn "%s" message
| None -> printfn "%d" number

Nobody likes duplicated effort. The only difference between these lines of code and the isEven printing code is the checker function. This is where a higher order functions come in. A higher order function takes a function as an input or returns a function as the output.

let numberCheckerPrinter (numberChecker : NumberChecker) number =
    match numberChecker number with
    | Some message -> printfn "%s" message
    | None -> printfn "%d" number

The first argument to this function is annotated as a NumberChecker, which we defined at the top of our program. We can pass into this function any number checker function we like and it will either print the message (if one is returned) or the number on its own.

numberCheckerPrinter isEven 2
numberCheckerPrinter isEven 3
numberCheckerPrinter isOdd 2
numberCheckerPrinter isOdd 3

This has this output:

That number's even!
3
2
That number's odd!

Note that the first argument (which happens to be a function) is passed to the function in the same way as the second argument (which happens to be an integer).

We could go on defining number functions in the way, but we’re already beginning to repeat ourselves. The definition of the higher order function was a function that took a function as an input or returned a function. It would nice if the programming language could some of the work for us and make number checkers. All that stays the same from number checker to number checker is that they all must accept an integer and return either a message or nothing.

We might have a number of number checkers that vary only in that they check a different divisor and have a different message.

let divisorNumberChecker (divisor, message) number = 
    if number % divisor = 0 then
        Some message
    else    
        None

Note that this function does not conform to the NumberChecker type that is defined at the top as it takes two arguments: a tuple of the divisor and the message and the number. We can use this function to make new number checkers by fixing the first input with partial function application.

let fizz = divisorNumberChecker (3, "Fizz!")

Even though divisorNumberChecker takes two arguments, we only supplied the first. This causes F# to return a new function which accepts the remaining argument and has fixed the first argument.

Running this in F# interactive gives the type of fizz, which matches NumberChecker.

> 

val fizz : (int -> string option)

Making the “Buzz!” checker is simply:

let buzz = divisorNumberChecker (5, "Buzz!")

We have functions for the “Fizz!” and the “Buzz!” part of the game, we now need to deal with the case when the number is divisible by 3 and 5. We could define a function to do this, but this a duplicated effort that we want to avoid. After all we have fizz and buzz, we want to reuse them.

let andNumberChecker (f : NumberChecker, g : NumberChecker) x  = 
    match f x, g x with
    | Some messageF, Some messageG -> messageF + " " + messageG |> Some
    | _ -> None

The andNumberChecker lets us combine two number checker functions into one. If both functions return a message for the given number, then it joins the messages together and returns them. Otherwise, it returns None.

Again, I’ve use partial function application to fix the fizz and buzz functions to make fizzBuzz.

let fizzBuzz = andNumberChecker (fizz, buzz)

So far, I’ve been passing single functions as arguments to other functions. Functions can be treated as other objects in F#. Therefore, we can put them into a list and pass that list to a function. This way we can keep checking the same number with different checkers and use the message from the first one that returns something rather than nothing:

let doManyChecks (numberCheckers : NumberChecker list) number =
    let message = 
        List.fold (fun message numberChecker ->
            match message with 
            | Some _ -> message
            | None -> numberChecker number
        ) None numberCheckers
    match message with
    | Some message' -> printfn "%s" message'
    | None -> printfn "%d" number   
 
let doFizzBuzzChecks = doManyChecks [ fizzBuzz; fizz; buzz ]

We can use this to play the game:

doFizzBuzzChecks 3
doFizzBuzzChecks 4
doFizzBuzzChecks 5
doFizzBuzzChecks 15

In FSI:

Fizz!
4
Buzz!
Fizz! Buzz!

Or to play the game with many numbers:

[ 1 .. 30 ] |> List.iter doFizzBuzzChecks

The complete code for this can be found here:

https://github.com/robert-impey/CodingExperiments/blob/master/F-Sharp/Loose/FizzBuzz.fsx

Functional programming has been described as a non-solution to a non-problem. Compared to the for loop in C#, this looks like a lot of work. If you have a problem as simple as Fizz! Buzz!, then it’s best to stick to the simplest solution. However, many interesting problems are much more complicated.

Higher order functions allow for abstracting away the details and generalising code. We might add a rule of saying “Boom!” for primes. The code such a checker might be complicated and require extensive testing. The code that makes use of the checkers does not need to change in order to use this new checker, we simply add the function to the list of checkers. We can also combine it with other checkers, enabling code reuse. Functional programming is getting increasing attention because it allows programmers to closely focus their attention on just their problem and decouple that code from the part of the program that will make use of it.