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!

FizzBuzz with F#

Once again, I'm going to give a solution to the fizz buzz problem, but this time in a, for me, completely new language - F#!

I've been following the articles on Why I Love F# by Dustin Campell, but even though I was inspired by the language, I never got to download F# and try it... until this very day! I installed it an hour ago, experimented some, and just have to share my experience. As a first mission I tried to write a solution for the fizz buzz problem, and (with some basic knowledge from haskell programming) it didn't take me too long to find a solution. Here it is:

let fizzBuzz (x:int) = 
 match x with
 | x when x % 15 = 0 -> "FizzBuzz"
 | x when x % 3 = 0 -> "Fizz"
 | x when x % 5 = 0 -> "Buzz"
 | x   -> x.ToString()

let main = System.Console.WriteLine(String.concat "\n" (List.map fizzBuzz [1..100]))

More or less the same solution as the one given by bugrit in the last post. The fizzBuzz function takes an integer and returns the fizzbuzz string representation of that number, using pattern matching. Unfortunate, you have to specify the type of the argument because F# can't infer the type when using x.ToString() (because ToString() is a member function of object, which can be of any type).

The main function uses String.concat to concatenate the strings returned by fizzBuzz. In F#, all basic functions are put in libraries, which as prefixed with their name, such as String and List. They resemble namespaces in C# a lot, and by using the open keyword you can use all functions in a given library globally, without the prefix.

There are a lots of more stuff to find out about the language, for example how to integrate it with your current C# project. I'll blog about it if I have time to try it out!

What is your favorite language?

We all have our favorite language, but for most people it's almost religious to discuss which language is the best. I realized I don't know what language people really prefer, simply because I've never discussed it!

Having a look at TIOBE Programming Community Index for May 2008 got me thinking. You will see Java in top, followed by C and then (Visual) Basic. I couldn't get this, until I read the following:

Observe that the TIOBE index is not about the best programming language or the language in which most lines of code have been written.

Of course, Java produces a lots of lines of code, and C has been around for a long long time. Visual Basic I can't say why is rated third, but I guess every newbie programmer develops in VB, and also, you have all those macros! I guess those makes up for a few lines?! :)

C# is only at 8'th place, but I hope that's because you don't need to write as much code in it as you do with other languages... which probably isn't true because you DO write a lots of code in it. With C# 3.0 you can use synthetic sugar to write less code, but not that much ;) I really think the reason C# is not being that highly ranked is because it hasn't been around for that long. People are still experimenting with it, and those companies that has been around for a while can't see the reason for replacing Java with C#. But, in the future, when everyone is jumping off Java, C# will grow in popularity!

Anyway, I added a vote to this blog (in the left sidebar), so go ahead and vote on your favorite language. And, if you want, post a comment on this post, arguing for why you think your language is the best!

C# Lambda Lazy List FizzBuzz :)

Ok, so here is my next example of an implementation of the FizzBuzz problem. I'm going to use a combination of C# 3.0's lambda expressions, lazy lists and extension methods!

First, I create a function returning a lazy list over all numbers starting from 1:

static IEnumerable<int> AllNumbers()
{
    int i = 1;
    while (true) yield return i++;
}

Second, I create a function returning a lazy list of strings, being pText every pCount time. I.e. null, null, Fizz, null, null, Fizz.

static IEnumerable<string> FizzBuzz(int pCount, string pText)
{
    while (true)
    {
        for (int i = 0; i < pCount-1; i++)
        {
            yield return null;
        }
        yield return pText;
    }
}

Now, I need a way of combining the values two lists, so I create an extension method for this. It takes another list and a combinator function:

static IEnumerable<T> Combine<T, TA, TB>(this IEnumerable<TA> pA, IEnumerable<TB> pB, Func<TA, TB, T> pCombineFunc)
{
    var i = pA.GetEnumerator();
    var j = pB.GetEnumerator();
    while(i.MoveNext() && j.MoveNext())
    {
        yield return pCombineFunc(i.Current, j.Current);
    }
}

And here is the whole FizzBuzz program, returning a list of strings being 1, 2, Fizz, 4, Buzz...:

static IEnumerable<string> FizzBuzz()
{
    return AllNumbers().Combine(
        FizzBuzz(3, "Fizz").Combine(FizzBuzz(5, "Buzz"), (x, y) => x + y),
        (x, y) => (y != "") ? y : x.ToString());
}

To write the result to the console, I use this main function:

static void Main(string[] args)
{
    foreach (string fizzBuzz in FizzBuzz().Take(100))
    {
        Console.WriteLine(fizzBuzz);
    }
}

Thats it! Nice and easy eh? :) Hope you liked it and perhaps makes you look into C# 3.0, if you haven't already? You can always download Visual Studio 2008 C# Express for free if you want to try it out!

Edit: Changed generic parameters <T> to html-characters. Changed C# 3.5 to 3.0 (thank u Gustaf :))

C# FizzBuzz :)

Here is my thoughts and solution to Gustafs Functional FizzBuzz problem! It's more or less a copy from what I wrote as a comment in his old blog, except for some modifications in the code snippet below.

I believe that in almost all cases, where you should write a solution for a given problem, you have two solutions to choose from. The first one focuses on writing well looking, readable, code (which is always good), the second focuses on writing fast code (which is required in some projects).

My solution for a bit faster code (I guess), would be this (c# style):

for (int i = 1, j = 1, k = 1; i <= 100; i++, j++, k++)
{
    string t = "";
    if (j == 3)
    {
        t = "Fizz";
        j = 0;
    }
    if (k == 5)
    {
        t += "Buzz";
        k = 0;
    }
    if (t == "")
    {
        t = i.ToString();
    }
    Console.WriteLine(t);
}

The difference is that you don't need to call "x `mod` m == 0" to find out if you should print Fizz or Buzz, instead two extra counters are used to keep track on when to write Fizz and when to write Buzz. I guess you could write this in functional style as well, but my haskell skills are a bit out of date so I wouldn't dare to try that ;)

On "Java, Improve or Renew", Java Posse #182

So, the "dual post" from me and Christian has not yet been produced (we need to drink coffee together more often!). It's not really so that my fingers are itching - on the contrary; I've been writing on my thesis report like never before. The part I'm writing right now is about Domain Specific Languages, where focus is on writing internal DLS in Java. But right now, I feel like writing something short about something else..

I listened to on of the Java Posse podcasts yesterday. Its title was "Java, Improve or Renew?". I've actually started to listen to a lot of other podcasts (other than Hanselminutes and .NET Rocks), a complete list with reviews will come in a later post. I like the "Roundup" discussions of Java Posse a lot! There's so much people in the room, it sometimes impossible to identify who's who, but the good thing is that their opinions about the specific topics are so strong!

So, the "Improve or Renew" podcast was very interesting because to me it seemed like a quick (72 minutes) summary of what challenges Java has right now, to meet the future demands on the language. And not only about the language, but of course also about the bytecode itself.

There's so many factors to put into account for when changing/improving a language! Breaking backward compatibility is very painful when you're the biggest business software language in town, so that should be avoided as long as possible. When listening to the show, it seems like the question of closures in Java 7 really boils down to the implementation of generics in Java. .NET and Java has different implementations of generics and this is the reason that .NET had no problems putting lambdas (anonymous delegates) in - the generics implementation is the whole way down to the IL. It will indeed be very interesting to follow how the Java community deals with this question, but (as someone in the Java Posse panel points out) closures without a proper generics implementation will be a "half-baked" concept that's likely to make people disappointed.

Notice that I'm not trying to say that .NET is better choice than Java in any way! There's a lot more things to a language than small (but important) language details. Certainly no companies (or at least very few) are going to abandon Java in favor of .NET just because of the differences of generics, but it adds one more argument to the discussion of choosing framework (for you who have that choice).

But honestly, I must admit that Wes Dyer's post on monads in C# ("The Marvel of Monads") was really inspiring stuff. Monads in Java seems to be a far away, but I guess it's up to the Java community to decide on the "whats, whys and whens" on creating the proper building blocks for enabling them.