Friday, May 23, 2008

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!

4 comments:

Christian Genne said...

Niiice post :)

Looks like a functional version of the C# lazy list version I gave two posts ago, together with some funtional practices. Did you design it with my solution in mind, or was it just a coincidence that we used similar approaches? "Great minds think alike"! :)

I like the way you extend the language with uncurry3, typical haskell style in my opinion - if you are missing a core method, it will only take you a few seconds to add it. Also, for you who don't know haskell, you can skip the type declarations of most functions, right?

The combine function gets me a bit confused though, pattern matching "null ret"? I believe that matches when ret is null? And thus, "" ++ "" equals to null?

What I especially like with your implementation is the resultInf function, that's where all the magic goes :) "(uncurry3 combine) (zip3 ...)", nice!

I read the article on MinimalInterface, and agree that that's a good way of thinking when designing, but where do you put all your utility functions? But question don't belong in this comment, I'll blog about it instead ;)

Now, time for me to watch the "Don't fear the monads"!

Gustaf Nilsson Kotte said...

"Did you design it with my solution in mind, or was it just a coincidence that we used similar approaches?"

Actually, when I talked to you about this before your party, this version was already written.. :)

"Also, for you who don't know haskell, you can skip the type declarations of most functions, right?"

Yep, in most cases you can skip type declarations. Though, sometimes when dealing with monads with "too loose" type parameters, you need to give some hints to ghc..

null is the same as (in OO notation) list.isEmpty(), so "null ret" just checks if we got a result for either fizz, buzz, or both.

By the way, there's many other good videos at channel9, especially those with Erik Meijer..

Anonymous said...

I like the way you extend the language with uncurry3, typical haskell style in my opinion - if you are missing a core method, it will only take you a few seconds to add it. Also, for you who don't know haskell, you can skip the type declarations of most functions, right?

Anonymous said...

cool blog!