» Laziness and fizzbuzz in Haskell #

Paul R. Brown @ 2007-01-24

After peeking at Reg's solution, I can't resist posting a fizzbuzz implementation in Haskell (because Reg's looks stylistically like it should be written in an FP language of some flavor). It's also an example of the surprising effectiveness of being lazy. Some Haskell:

module Main(main) where

import List

f :: Int -> String
f x | (x `mod` 15 == 0) = " fizzbuzz"
    | (x `mod` 5 == 0) = " buzz"
    | (x `mod` 3 == 0) = " fizz"
f 1 = "1"
f x = ' ':(show x)

main :: IO ()
main = (putStr.concat) (map f [1..100])

Here's a slightly different version of the main function:

main' :: IO ()
main' = mapM_ putStr (map f [1..100])

So, which one is better? Interestingly, if you crank up the 100 to 10000000 (108), either one of those two versions runs in well under a minute, in <2MB of (resident) memory, and presents roughly the same heap profile:


main


main'

The main' version might naively appear to be faster than the main version, but this is laziness in action: a String is [Char], i.e., a list of characters. The list of characters passed to putStr in the main version is generated lazily, as are the IO actions in the main' version. (In fact, the main version is faster at under 7 seconds to roughly 20 seconds for the main' version.) As you would expect based on laziness, both programs begin producing output immediately upon execution. Meanwhile, without laziness, the ruby version chews up gobs of memory and takes a long time. (I got tired of waiting for it after about 30 minutes, at which point it was using 35M of resident memory without producing any output.) The simplest possible ruby solution (for loop, if...elsif...else) runs in around 45 seconds and consumes <2M of resident memory.

As an aside, reproducing the precise flavor of Reg's solution would mean composing a list of functions, which is simply expressed in Haskell terms and wouldn't impact laziness. If l is of type [Int -> Int] (a list of functions that map integers to integers), then:

foldr (.) id l

is the Int -> Int that applies the composition of the elements of l on the left, i.e., last l is the first function applied. Nonetheless, precisely the same solution (repeatedly applying a function parameterized by a modulus and a substitution) isn't as simply expressed because String and Int are distinct types.

Update: There is a thread going on reddit that has some terse Haskell versions, along with versions for a bunch of other languages.

 

← 2006-12-22 — Secret Santas in Haskell III: Lather, Rinse, Repeat
→ 2007-02-24 — Review of "Programming in Haskell"