## Monday, June 08, 2020

### I can code that FizzBuzz function with only two tests

My favorite implementation of FizzBuzz is
the Ruby version based upon nothing more than
lambda calculus and Church numbers,
*i.e.* nothing but functions all the way down.

Then I saw an interesting version of it in the presentation “Clean Coders Hate What Happens to Your Code When You Use These Enterprise Programming Tricks.” The normal implementation usually involves thee tests, one for divisibility by 3, one for divisibility by 5, and an annoyingly extra one for both or for divisibility by 15. But the version given in the presentation only had two tests. Here's a version of that in Lua:

function fizzbuzz(n) local test = function(d,s,x) return n % d == 0 and function(_) return s .. x('') end or x end local fizz = function(x) return test(3,'Fizz',x) end local buzz = function(x) return test(5,'Buzz',x) end return fizz(buzz(function(x) return x end))(tostring(n)) end for i = 1 , 100 do print(i,fizzbuzz(i)) end

The function `test()`

will return a new function that returns a string,
or whatever was passed in `x`

.
`fizz()`

and `buzz()`

are functions that return what `test()`

returns.
The last line can be broken down into the following statements:

_0 = function(x) return x end _1 = buzz(_0) _2 = fizz(_1) _3 = _2(tostring(n)) return _3

And we can see how this works by following a few runs through the code.
Let's first start with a number that is *not* divisible by 3 or 5,
say, 1.

_0 = function(x) return x end _1 = buzz(_0) = function(x) return x end _2 = fizz(_1) = function(x) return x end _3 = _2("1") == "1" return _3

`_0`

is the identity function—just return whatever it is given.
`buzz()`

is called,
which calls `test()`

,
but since the number is not divisible by 5,
`test()`

returns the passed in identity function,
which in turn is returned by `buzz()`

.
`fizz()`

is then called,
and again,
since the number is not divisible by 3,
`_test()`

returns the identity function,
which is returned by `fizz()`

.
`_3`

is the result of the identity function called with “1”,
which results in the string “1”.

Next, the number 3 is passed in.

_0 = function(x) return x end _1 = buzz(_0) = function(x) return x end _2 = fizz(_1) = function(_) return 'Fizz' .. _1('') end _3 = _2("3") == 'Fizz' return _3

`_0`

is the identify function.
`buzz()`

just returns it since 3 isn't divisible by 5.
`fizz()`

,
however,
returns a new function,
one that returns the string “Fizz” concatenated with the empty string as returned by the identify function.
This function is then called,
which results in the string “Fizz”.

The number 5 works similarly:

_0 = function(x) return x end _1 = buzz(_0) = function(_) return 'Buzz' .. _0('') end _2 = fizz(_1) = function(_) return 'Buzz' .. _0('') end _3 = _2("5") == 'Buzz' return _3

Here,
`buzz()`

returns a new function which returns the string “Buzz” concatenated with the empty string returned by the identify function.
`fizz()`

returns the function generated by `buzz()`

since 5 isn't divisible by 3,
and thus we end up with the string “Buzz”.

It's the case with 15 where all this mucking about with the identify function is clarified.

_0 = function(x) return x end _1 = buzz(_0) = function(_) return 'Buzz' .. _0('') end _2 =_fizz(_1) = function(_) return 'Fizz' .. _1('') end _3 = _2("15") = 'FizzBuzz' return _3

Again,
`_0`

is the identify function.
`buzz()`

returns a new function because 15 is divisible by 5,
and this function returns the string “Buzz” concatenated by the empty string returned by the identity function.
`fizz()`

also returns a new function,
because 15 is also divisible by 3.
This function returns the string “Fizz”, concatenated by the passed in function,
which in this case is *not* the identity function,
but the function returned from `buzz()`

.
This final function returns “Fizz” concatenated with the string of the function that returns “Buzz” concatenated with the empty string returned by the identity function,
resulting in the string “FizzBuzz”.

Yes, it's quite a bit of work just to avoid an extra test, but fear not! Here's a way to do FizzBuzz with just two tests that is vastly simpler:

function fizzbuzz(n) local list = { 'Fizz' , 'Buzz' , 'FizzBuzz' } list[0] = tostring(n) local m = (n % 3 == 0 and 1 or 0) + (n % 5 == 0 and 2 or 0) return list[m] end for i = 1 , 100 do print(i,fizzbuzz(i)) end

Here we generate an index into an array of four possible responses, the original number as a string, “Fizz”, “Buzz” and “FizzBuzz”. If the number isn't divisible by either 3 or 5, the index is 0; if it's divisible by 3, the index is 1, if divisible by 5, the index is 2, and if both, the index ends up as 3. It's not quite as mind blowing as the first version, but it is easier to translate to a language that lacks closures, like C.