Lazy FizzBuzz in Haskell

Christian has been writing too many FizzBuzzes [1,2,3] right now, without me responding! We also got a comment in the first fizzbuzz post from sganslandt I've actually had the code for this post for two weeks now, but haven't had the time to finish it.

The post is based on lazy evaluation, but the neat thing is that is the default behavior in Haskell, in contrast too most other languages. Among other things, lazy evaluation allows you to reason in another way when construcing you software.

Having lazy evaluation in a language makes it "kind of important" to have control over the side-effects, so lazy evaluation and pure functions live in symbiosis in Haskell.

Let's start out with a regular divides..

> divides m n = m `mod` n == 0

We then construct a function that takes a divisor, a string, a number, and returns a string. Note that the number is the last argument.

> genWord :: Int -> String -> Int -> String
> genWord x str i
>  | i `divides` x = str
>  | otherwise = ""

Now the fun begins! We can generate infinite lists with "fizzes" and "buzzes", just by mapping genWord over an infinite list.

> fizzes = map (genWord 3 "Fizz") [1..]
> buzzes = map (genWord 5 "Buzz") [1..]
> nums = [1..]

So, for example, the first ten elements of fizzes looks like this:

["","","Fizz","","","Fizz","","","Fizz",""]

Now, having three infinite lists, we need to combine those to one infinite list. Is this hard to digest? I guess it's not the "normal routine" that one follows when constructing imperative programs. So, how could this in any way be useful outside the esoteric world of academia? Let us talk a bit more on that after all code, focusing on one thing at a time. Here's combine:

> combine :: String -> String -> Int -> String
> combine str1 str2 n
>  | null ret = show n
>  | otherwise = ret
>  where ret = str1 ++ str2

In other words, we concatenate the "fizz" string with the "buzz" string and if the concatenated string is empty, we return a number instead (as a string). This makes the case of "n%15" unnecessary, which is nice. The idea for creating combine is that if we know how to combine one element, we are much closer to a solution for our problem. Though, we do restrict ourselves when defining the type for combine. The only requirement for "n" is that it is showable, but the example is just much more clearer when not using parametrized types..

A problem left to solve is the problem of having "a bunch of lists" and returning one list. The function zip does exactly that, and zip3 is function that takes three lists and returns a list of triples (source here).

From ghc's Prelude documentation:

zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
zip3 takes three lists and returns a list of triples, analogous to zip.

Now, we could rewrite combine to take a triple instead of three arguments. Currying is perhaps not well-known concept, but essentially it is another way of applying arguments to a function:

f(x,y) // Normal style (un-curried)
f x y -- Curried

So, we define a function, uncurry3, which takes a function (with three arguments) as the first argument, and returns a function which takes one argument, a triple. A funny thing is that the type declaration is longer than the implementation:

> uncurry3 :: (a -> b -> c -> d) -> ((a, b, c) -> d)
> uncurry3 f (a,b,c) = f a b c

Here's the "grande finale"! We apply fizzes, buzzes and nums to zip3, giving an infinite list of triples. We then map the uncurried function (of the "third order") on that infinite list, giving an infinite list of fizzbuzzes with numbers in between.

> resultInf :: [String]
> resultInf = map (uncurry3 combine) (zip3 fizzes buzzes nums)

Finally, we take the first 100 elements of the infinite list, and print it to stdout.

> result100 :: [String]
> result100 = take 100 resultInf

> printResult :: IO ()
> printResult = mapM_ putStrLn result100

The complete program is 15 lines of code, exclusive type type declarations, and I argue that the code is easy to read and understand. So, let us talk about why we want to create an esoteric and academic example like this, but first a quick recap..

divides is the mathematical operator '|'

genWord is a rule for generating words

fizzes, buzzes and nums generates sets of values

combine is a rule for combining three elements into one

uncurry3 converts a curried function to function of triples

result100 and printResult deals with presenting the result

Do you see the trace of math here? We treat the lists as sets and define some transformations which makes it easier to reason about the problem, in the spirit of Poyla. We decompose the problem into smaller sub-problems, which makes it much more easy to reason about the program. Separation of Concerns (SoC) is an OO principle that advocates exactly this.

When I think about it, OO has a lot of nice principles which improves the quality of the software, but I argue that OO is extremely hard to get right! Principles such as LawOfDemeter, SoC, MinimalInterface and the Liskov substitution principle, are just a few principles which (often) make good OO software, but are hard to get right all at once. Further, I'm not convinced that these principles are discussed among developers in their daily work, if the developers don't have a "pattern background" or in other ways are interested in OO design. Time pressure is probably the killer here. What is discussed on your (developer) meetings at work?

Finally, if you haven't seen it, watch Brians Beckman's "Don't fear the monads" on Channel9.

Note: as before, this post is written in Literate Haskell, which means that you can save the entire content in this post, paste it into a file and load that file with ghci. Try it!

Update: You might want to read Don Stewart's post (called "Haskell is a strict language") on the optimizations that's going on in ghc. Very nice!