It’s a Bank Holiday here in the UK and that’s the traditional time when Systems People take to their retreats and work on their Foo.
Since Functional Programming is all the rage at the moment I thought I’d take everybody’s favourite interview test and give it an FP makeover.
We’ll use elm to start with because it’s a nice, simple ML language and has a neat REPL with great error messages if you mess up:
> foobar: String
| foobar = 14
|
-- TYPE MISMATCH ---------------------------------------------------------- REPL
Something is off with the body of the `foobar` definition:
10| foobar = 14
^^
The body is a number of type:
number
But the type annotation on `foobar` says it should be:
String
Hint: Try using String.fromInt to convert it to a string?
>Before we start hacking, let’s have a look at the problem specification.
Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.
What we have here is a conditional transform of a list of integers. And transforms are what FP is really good at. So let’s break it down into primitives, FP style, then build them up into a solution.
First we need a function that takes an integer and produces a string if the integer is a multiple of three. That bit is straightforward. The question is what should that function produce if the integer isn’t a multiple of three?
Well, nothing.
In other words when we call this function, we may get a string and we may
get nothing. We can model that in elm very easily using the Maybe type.
Let’s give elm the type specification we want
> fizz: Int -> Maybe String
| fizzand then complete the definition
> fizz: Int -> Maybe String
| fizz x = if modBy 3 x == 0 then Just "Fizz" else Nothing
|
<function> : Int -> Maybe String
>The definition for Buzz is pretty much the same
> buzz: Int -> Maybe String
| buzz x = if modBy 5 x == 0 then Just "Buzz" else Nothing
|
<function> : Int -> Maybe String
>Let’s check they do what we expect
> fizz 10
Nothing : Maybe String
> fizz 6
Just "Fizz" : Maybe String
> buzz 10
Just "Buzz" : Maybe String
> buzz 6
Nothing : Maybe String
> buzz 15
Just "Buzz" : Maybe String
> fizz 15
Just "Fizz" : Maybe String
>Lovely. All as expected.
But we can do better than that. Note how similar the two function
definitions are. That means there is a more abstract function that can do
both. What we need is a function that takes a divisor as a number and an
output as a string as well as the number to check. Then we can do both
fizz and buzz with the same function. Let’s pass these meta-parameters
in as a tuple.
> fbTransform: Int -> (Int, String) -> Maybe String
| fbTransform x (mod, val) =
| if modBy mod x == 0 then Just val else Nothing
|
<function> : Int -> ( Int, String ) -> Maybe String
>When we test we get
> fbTransform 6 (3, "Fizz")
Just "Fizz" : Maybe String
> fbTransform 6 (5, "Buzz")
Nothing : Maybe String
> fbTransform 10 (3, "Fizz")
Nothing : Maybe String
> fbTransform 10 (5, "Buzz")
Just "Buzz" : Maybe String
>The fizz and buzz checks we need can be reduced to a simple list of tuples
> fizzBuzzMetaArguments: List (Int, String)
| fizzBuzzMetaArguments = [(3, "Fizz"), (5, "Buzz")]
|
[(3,"Fizz"),(5,"Buzz")]
: List ( Int, String )
>and we can map those arguments across the transform function to get the List of output
strings we want
> fizzBuzzMetaArguments |> List.map (fbTransform 30)
[Just "Fizz",Just "Buzz"]
: List (Maybe String)
> fizzBuzzMetaArguments |> List.map (fbTransform 10)
[Nothing,Just "Buzz"] : List (Maybe String)
>From this we can create a function that takes the meta arguments along
with the number to check and returns a List String, using filterMap
instead of map to pull the values out of the Maybe types. Once we
have that List we can manipulate it down into the output string we want.
To do that we need a couple of convenience functions. Firstly, a function
to generate the default of displaying the Integer as a String.
> orShow: Int -> Maybe String -> String
| orShow = String.fromInt >> Maybe.withDefault
|
<function> : Int -> Maybe String -> String
>and, secondly, a function to switch a string to a Maybe based upon
whether the String has anything in it
> stringNotEmpty: String -> Maybe String
| stringNotEmpty val = if String.isEmpty val then Nothing else Just val
|
<function> : String -> Maybe String
>then we can stream all the transformations neatly together
> fizzBuzzerCategory: List (Int, String) -> Int -> String
| fizzBuzzerCategory metaArgumentList x =
| metaArgumentList
| |> List.filterMap (fbTransform x)
| |> String.concat
| |> stringNotEmpty
| |> (orShow x)
|
<function> : List ( Int, String ) -> Int -> String
>which we use to curry up the final transform function for FizzBuzz
> fizzbuzzer = fizzBuzzCategory fizzBuzzMetaArguments
<function> : Int -> String
>Final check
> fizzbuzzer 4
"4" : String
> fizzbuzzer 6
"Fizz" : String
> fizzbuzzer 10
"Buzz" : String
> fizzbuzzer 30
"FizzBuzz" : String
>So far so good. Now let’s bring it all together in a final FP flourish
> List.range 1 100 |> List.map fizzbuzzer
["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz","16",
"17","Fizz","19","Buzz","Fizz","22","23","Fizz","Buzz","26","Fizz","28","29","FizzBuzz","31",
"32","Fizz","34","Buzz","Fizz","37","38","Fizz","Buzz","41","Fizz","43","44","FizzBuzz","46",
"47","Fizz","49","Buzz","Fizz","52","53","Fizz","Buzz","56","Fizz","58","59","FizzBuzz","61",
"62","Fizz","64","Buzz","Fizz","67","68","Fizz","Buzz","71","Fizz","73","74","FizzBuzz","76",
"77","Fizz","79","Buzz","Fizz","82","83","Fizz","Buzz","86","Fizz","88","89","FizzBuzz","91",
"92","Fizz","94","Buzz","Fizz","97","98","Fizz","Buzz"] : List String
>Tada.
The second part of the test arrives
now alter the program so that multiples of 7 print “Woof”
No problem
> fizzbuzzer = fizzBuzzerCategory (fizzBuzzMetaArguments ++ [(7, "Woof")])
<function> : Int -> String
> List.range 1 100 |> List.map fizzbuzzer
["1","2","Fizz","4","Buzz","Fizz","Woof","8","Fizz","Buzz","11","Fizz","13","Woof",
"FizzBuzz","16","17","Fizz","19","Buzz","FizzWoof","22","23","Fizz","Buzz","26",
"Fizz","Woof","29","FizzBuzz","31","32","Fizz","34","BuzzWoof","Fizz","37","38",
"Fizz","Buzz","41","FizzWoof","43","44","FizzBuzz","46","47","Fizz","Woof","Buzz",
"Fizz","52","53","Fizz","Buzz","Woof","Fizz","58","59","FizzBuzz","61","62","FizzWoof",
"64","Buzz","Fizz","67","68","Fizz","BuzzWoof","71","Fizz","73","74","FizzBuzz","76","Woof",
"Fizz","79","Buzz","Fizz","82","83","FizzWoof","Buzz","86","Fizz","88","89","FizzBuzz","Woof",
"92","Fizz","94","Buzz","Fizz","97","Woof","Fizz","Buzz"] : List String
>Done
You don’t need to use a pure functional language to take advantage of this approach. Ruby, for example, has many of the features of a functional language, with more arriving with every version.
Here’s the Functional Fizzbuzz approach in Ruby.
def fb_transform(x, (mod, val))
val if (x % mod).zero?
end
def fizz_buzz_arguments
[
[3, 'Fizz'],
[5, 'Buzz']
]
end
def fizzbuzzercategory(meta, x)
case meta.filter_map { |arr| fb_transform(x, arr) }
in []
x.to_s
in arr
arr.join
end
end
def fizzbuzzer(x)
fizzbuzzercategory(fizz_buzz_arguments, x)
end
def run
(1..100).map { |x| fizzbuzzer(x) }
end
puts
puts run.inspect
def fizzbuzzer(x)
fizzbuzzercategory(fizz_buzz_arguments << [7, 'Woof'], x)
end
puts
puts run.inspectRunning this gives
$ ruby fizzbuzz.rb
fizzbuzz.rb:21: warning: Pattern matching is experimental, and the behavior may change in future versions of Ruby!
["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz",
"11", "Fizz", "13", "14", "FizzBuzz", "16", "17", "Fizz", "19",
"Buzz", "Fizz", "22", "23", "Fizz", "Buzz", "26", "Fizz", "28",
"29", "FizzBuzz", "31", "32", "Fizz", "34", "Buzz", "Fizz", "37",
"38", "Fizz", "Buzz", "41", "Fizz", "43", "44", "FizzBuzz", "46",
"47", "Fizz", "49", "Buzz", "Fizz", "52", "53", "Fizz", "Buzz",
"56", "Fizz", "58", "59", "FizzBuzz", "61", "62", "Fizz", "64",
"Buzz", "Fizz", "67", "68", "Fizz", "Buzz", "71", "Fizz", "73",
"74", "FizzBuzz", "76", "77", "Fizz", "79", "Buzz", "Fizz", "82",
"83", "Fizz", "Buzz", "86", "Fizz", "88", "89", "FizzBuzz", "91",
"92", "Fizz", "94", "Buzz", "Fizz", "97", "98", "Fizz", "Buzz"]
["1", "2", "Fizz", "4", "Buzz", "Fizz", "Woof", "8", "Fizz", "Buzz",
"11", "Fizz", "13", "Woof", "FizzBuzz", "16", "17", "Fizz", "19",
"Buzz", "FizzWoof", "22", "23", "Fizz", "Buzz", "26", "Fizz",
"Woof", "29", "FizzBuzz", "31", "32", "Fizz", "34", "BuzzWoof",
"Fizz", "37", "38", "Fizz", "Buzz", "41", "FizzWoof", "43", "44",
"FizzBuzz", "46", "47", "Fizz", "Woof", "Buzz", "Fizz", "52", "53",
"Fizz", "Buzz", "Woof", "Fizz", "58", "59", "FizzBuzz", "61", "62",
"FizzWoof", "64", "Buzz", "Fizz", "67", "68", "Fizz", "BuzzWoof",
"71", "Fizz", "73", "74", "FizzBuzz", "76", "Woof", "Fizz", "79",
"Buzz", "Fizz", "82", "83", "FizzWoof", "Buzz", "86", "Fizz", "88",
"89", "FizzBuzz", "Woof", "92", "Fizz", "94", "Buzz", "Fizz", "97",
"Woof", "Fizz", "Buzz"]Note how I’ve sneaked in the new Ruby 2.7 pattern matching syntax in the case statement, argument deconstruction and a filterMap. Bonus Foo for reading this far!
And there we have it. A slightly different take on an old problem. A Goldilocks version if you like. Not too Abstract. Not too Concrete. Just right.
After a few more decades of Foo Quests like this I might get close enough to Nirvana to really understand Lisp.
If you want to quickly fire up an Ubuntu Focal image so you can play with elm or Ruby 2.7, you can sign up for Brightbox in just a couple of minutes and use your ÂŁ50 free credit to give it a go.