We’re not in Kansas anymore, Toto

Beginners in Haskell often get stuck with the design and pragmatics issues. For me, the golden rule is this: think about data structures.

By this I mean: work out what data structures you’d like to use, and think about the various ways you’d like to transform your data (e.g. from a list of words to a binary search tree to a list of sorted words). And be confident in your ideas, and don’t get derailed by worrying how exactly to do each step (you will often find that big, hard steps break into small, easy steps – just have patience). Languages like Haskell really do promote thinking in these terms, rather than the details of what gets done when and to whom etc, and I think this makes for a much more powerful way to program.

Here’s an example of thinking in data structures, rewriting a standard example in a way you might never have seen, not a div in sight – but in a way that I think is much closer to the spirit of the game/problem. I give you: Fizz Buzz.

The task is is – you want Fizz every three steps, and Buzz every five steps, and sometimes the cycles coincide. Let’s talk cycles then.

threes = cycle ["", "", "Fizz"]
fives  = cycle ["", "", "", "", "Buzz"]

where ‘cycle’ is defined like this (the real library def is more efficient, but less clear)

cycle xs = xs ++ cycle xs     -- SIMPLE version of lib

So “threes” just spits out [“”,””,”Fizz”,””,””,”Fizz”,… ] until we stop it, and similarly for “fives”. Next, we want to merge two streams into one: this is quite common so there’s a library function for it. To cut a long story short, “zipWith” pairs up elements and uses some  operation to combine each pair,

zipWith g [a,b,c,...] [d,e,f, ...]  ===> (computes to)  [g a d, g b e, g c f, ...]
zipWith max [1,2,3] [2,2,2] ===> [2,2,3]
zipWith (*) [1,2,3] [2,2,2] ===> [2,4,6]

Think zippers, of course. Now, that’s just what we want for merging our streams. It works for infinite streams too.

fizzbuzz = zipWith (++) threes fives

(++) is string concatenation, and then we just push the list of lines to the screen. And hit ^C when we get bored.

main = putStr (unlines fizzbuzz)

If we want numbers in there between the fizzes and buzzes, we can just zip in another list that contains the indices, and just add in that info if the string would otherwise be empty. Notice: still working with data structures.

So: it’s a short piece of code which obviously works, built from small pieces and glued together in a simple way, and there’s no worry about loops, division, memory limits, … I like programming like this!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s