Saturday, February 25, 2012

Anatomy of a One-Liner: FizzBuzz in Haskell

In the NashFP group, a gang of functionally inclined Nashville area geeks recently organized by Bryan Hunter, we decided to share implementations of the classic FizzBuzz problem in various functional languages. I took my first shot in Scheme and then decided it was time to dust off my Haskell. On my first attempt I waded through the syntax enough to get something working, but it included several named functions and was clearly more code than was necessary to solve the problem. As I began to look for ways to shorten it, I remembered that a year or two ago Bryan had written a FizzBuzz implementation in Erlang that was short enough to tweet. Obviously this became my new goal.

I managed to whittle it down below 140 characters, but its readability suffered quite a bit. I thought it might be fun to dissect here bit by bit, and it might even come out shorter and more readable. I keep learning new tricks in Haskell and in the general functional approach that offer new opportunities to make my code shorter and more streamlined. You might learn some of these here, or if you have any pointers to offer me in comments, I would love to learn some from you as well.

In case you're not familiar with FizzBuzz, it is a programming exercise in which goal is to list integers from 1 to 100, replacing those divisible by 3 with the term "Fizz," those divisible by 5 with the term "Buzz," and those divisible by both 3 and 5 with the term "FizzBuzz."

For this exercise I will be using my favorite IDE, the REPL, in this case GHCI, the Glasgow Haskell Compiler Interactive.

Let's start with the input range. We ultimately want to go from 1 to 100, but let's start with 1 to 15 just for brevity of output while we evolve this thing.
Prelude> [1..15]
To apply a function to each member of this list, we could use the map function or a list comprehension, which should be shorter, so let's try that. We'll start with a simple identity comprehension, which will do nothing for us. This step is just about making ourselves a place to do some work.
Prelude> [x | x <- [1..15]]
Let's try the Fizz substitution for multiples of 3. Note that the else case needs the show function to convert the integer to a string since Haskell lists must be homogenous.
Prelude> [if mod x 3 == 0 then "Fizz" else show x | x <- [1..15]]
Now for the Buzz case for multiples of 5:
Prelude> [if mod x 3 == 0 then "Fizz" else if mod x 5 == 0 then "Buzz" else show x | x <- [1..15]]
This works up through 14, but I hate to add another case, and it's already getting too long due to repetitive code. Under normal circumstances I might look to extract a method here, but we're working on a one-liner, so let's try another way. The factor mappings must be stated, and the most concise way I know is as a list of tuples.
Prelude> [(3,"Fizz"),(5,"Buzz")]
Now we need a way to iterate through this list, run the divisibility test, and make the appropriate substitutions. First off we need to give the mapping list a chance to dance with each element in the list of integers. We can do this by tucking it into a tuple with the integer inside the comprehension.
Prelude> [(x,[(3,"Fizz"),(5,"Buzz")]) | x <- [1..15]]
The resulting list can now be used as the input for another list comprehension, where we can take another shot at applying our divisibility tests. Once again we will start with an identity comprehension just to get our terms in place before we put them to work. Since each element of the list is a 2-tuple, we can go ahead and give each member a variable, f for factor and n for name.
Prelude> [(x,[(f,n) | (f,n) <- [(3,"Fizz"),(5,"Buzz")]]) | x <- [1..15]]
Now we can add a filter to the new comprehension to get only the pairs whose factor evenly divides the integer.
Prelude> [(x,[(f,n) | (f,n) <- [(3,"Fizz"),(5,"Buzz")],mod x f == 0]) | x <- [1..15]]
That's closer, but that comprehension is still returning the factor-name pair, and we're only interested in the name, so let's make that adjustment.
Prelude> [(x,[n | (f,n) <- [(3,"Fizz"),(5,"Buzz")],mod x f == 0]) | x <- [1..15]]
This is starting to bear some resemblance to the result we're after, but notice that our Fizzes and Buzzes are still coming out in lists. We might grab the head of the list, but the FizzBuzzes have two elements, and we don't want to drop one. We need to concatenate them, which we can do with the concat function.
Prelude> [(x,concat [n | (f,n) <- [(3,"Fizz"),(5,"Buzz")],mod x f == 0]) | x <- [1..15]]
Now we have a list of tuples, each containing one value that we want and another that we don't. First we'll add a show to the x to make them the same type so we can compare them.
Prelude> [(show x,concat [n | (f,n) <- [(3,"Fizz"),(5,"Buzz")],mod x f == 0]) | x <- [1..15]]
Now that the elements in the tuples are the same type, we can use the max function to make the choice between them.
Prelude> [max (show x) (concat [n | (f,n) <- [(3,"Fizz"),(5,"Buzz")],mod x f == 0]) | x <- [1..15]]
Now all that's left to do is to remove some readability spaces to squeeze it down and blow up our input range to give us 100 inputs instead of 15.
Prelude> [max(show x)(concat[n|(f,n)<-[(3,"Fizz"),(5,"Buzz")],mod x f==0])|x<-[1..100]]
78 characters. Not too bad. Please let me know if you see where I could shave off some more.

No comments:

Post a Comment