Wednesday, April 30, 2008

Functional FizzBuzz

Ok, so here's my first "real" post! It's a spin-off of the (perhaps) famous fizzbuzz/bizzbuzz test. There seems to be some consensus [1,2,3] that this kind of tests identify at least the worst developers during job interviews. When listening to one episode of Hanselminutes, I started to wonder how this would work in an interview for a company who would like to hire functional programmers.

My plan is to do some more posts on this theme in the future, but at what frequence I don't know yet. And of course I'll put other posts in between the "fizzbuzz" posts as well!

Think of this as a version of "The evolution of a Haskell programmer", but perhaps in a more "interviewish" context - that is: Does the style of a "functional fizzbuzz" say something about the person in front of me?

So, here's the first version! I call it "Imperative programmer likes Haskell" (but makes the wrong choice). It's written in literate way, so it should work to copy/paste the whole post directly into your text editor, save it (as *.lhs), and then load it into ghci or whatever you choose to run/compile Haskell programs in.

First, construct a small helper function for "divides"

> divides x m = x `mod` m == 0

Then do a simple "divide-and-conquer" solution, if we can print one "fizzbuzz", then we have solved the hardest task of this problem. As we see, the if-then-else expression doesn't really fit into the do-notation because of the indentation rules, which is the reason we have to use the block notation. The function looks a bit imperative and it's clearly abusing IO, printing directly to stdout. It would be better to collect the values before printing them, but lets take that in another post or perhaps skip it entirely..

> printOne x = do
>  {
>   if (x `divides` 3 && x `divides` 5) then print "FizzBuzz" 
>     else if (x `divides` 3) then print "Fizz" 
>     else if (x `divides` 5) then print "Buzz" 
>     else print $ show x
>  }

Now use a nice higher order function (HOF), which certainly no beginner would have found! This function takes a function of type a -> m a, the list [a] and performs the given actions on that list, returning no result. The entire type for mapM_ is: 
 Monad m => (a -> m b) -> [a] -> m ()
, where our monad m in this case is IO a

> fizzbuzz = mapM_ printOne [1..100]

The above function and its relatives are nice examples of "iterating" in Haskell. Of cource, some other languages have HOFs as well, and I think that I most likely will HOFs in other language in some later posts.

So, that's all for today folks! Challenge: Try writing some fizzbuzz's yourself in your favourite language and put them as a comment below or post them in your own blog and put a link to it in the comments.

1 comment:

sganslandt said...

#include <stdio.h>

int main(void) {
  int i,r;
  for (i = 1; i != 101; i++) {
    r = 0;
    if ((i % 3) == 0) { printf("Fizz"); r = 1; }
    if ((i % 5) == 0) { printf("Buzz"); r = 1; }
    if (!r) printf("%i",i);
    printf("\n");
  }
  return 0;
}

~

Challange: Create a poll to find out how many people find each code more readable! : )