* * * * *

            I can code that FizzBuzz function with only two tests

My favorite implementation of FizzBuzz [1] is the Ruby version [2] based upon
nothing more than lambda calculus [3] and Church numbers [4], i.e. nothing
but functions all the way down [5].

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 [6].” 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:

-----[ Luq ]-----
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
-----[ END OF LINE ]-----

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:

-----[ Lua ]-----
_0 = function(x) return x end
_1 = buzz(_0)
_2 = fizz(_1)
_3 = _2(tostring(n))
return _3
-----[ END OF LINE ]-----

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.

-----[ Lua ]-----
_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
-----[ END OF LINE ]-----

_0 is the identity function [7]—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.

-----[ Lua ]-----
_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
-----[ END OF LINE ]-----

_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:

-----[ Lua ]-----
_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
-----[ END OF LINE ]-----

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.

-----[ Lua ]-----
_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
-----[ END OF LINE ]-----

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:

-----[ Lua ]-----
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
-----[ END OF LINE ]-----

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.

[1] https://en.wikipedia.org/wiki/Fizz_buzz#Programming
[2] https://codon.com/programming-with-nothing
[3] https://en.wikipedia.org/wiki/Lambda_calculus
[4] https://en.wikipedia.org/wiki/Church_encoding
[5] https://en.wikipedia.org/wiki/Turtles_all_the_way_down
[6] https://www.youtube.com/watch?v=FyCYva9DhsI
[7] https://en.wikipedia.org/wiki/Identity_function

Email author at [email protected]

You are viewing proxied material from gopher.conman.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.