Sunday, January 18, 2009

Fizzbuzz and the State Monad

When I want to learn something I tend to look for examples that articulate the theme of the problem directly instead of making it accidentally complex. Simple examples make things easier, and I was searching for such an exmaple for understanding the State Monad in Haskell.

The State monad is useful for modeling computations in Haskell that maintain state, the bread and butter of programming in an imperative language. Haskell tutorials for beginners teach us how to pass on the old value of the state with each call of the function, and then extract the new state from the result. Commonly referred to as "threading the state through the computation", this strategy works, but tedius .. and Haskellers will consider this .. boilerplate.

The State monad raises the level of abstraction and decouples the state management from the computation itself. I am not going to write yet another tutorial on monads. Instead I would like to share the example problem which made me understand the State monad quite beautifully.

It is fizzbuzz !! Fizzbuzz has been solved in a multitude of languages of various paradigms. The basic problem that fizzbuzz solves is simple enough to be moulded into demonstrating various idioms of a programming language. Not all of them are efficient or elegant enough, but serves well articulating the idiom in hand - you don't have to stretch yourselves to comprehend the problem that you are trying to solve. You can focus on the solution itself right from the word go. Even Haskell has quite a few solutions to the fizzbuzz problem, but I could not find one that makes use of the State monad. The solution below generates the whole fizzbuzz sequence as a side-effect using monads. This is not the most elegant of solutions for fizzbuzz, does not work for infinite sequences, but I found it quite simple and useful in understanding the State monad in Haskell ..

Without further ado ..

import Monad
import Control.Monad.State

-- the entire fizzbuzz list is prepared as a side-effect
-- collect prepares the list as the State
-- mapM strips the values part

run_fizzbuzz :: [Integer] -> [[Char]]
run_fizzbuzz list =
    state where (_, state) = runState (do mapM_ collect list) []

collect :: Integer -> State [[Char]] ()

-- gets the old state and cons s the new
collect n = do 
    f <- get
    put ((fizzbuzz n):f)

fizzbuzz :: Integer -> [Char]
fizzbuzz n 
    | n `rem` 3 == 0 && n `rem` 5 == 0   = "fizzbuzz"
    | n `rem` 3 == 0                     = "fizz"
    | n `rem` 5 == 0                     = "buzz"
    | otherwise                          = show n

main :: IO ()
main = do putStr $ show $ reverse $ run_fizzbuzz [1..100]


Anonymous said...

Are you reading/have read Real World Haskell by any chance? Up until I started reading RWH it was hard for me to even find examples like yous here. Thanks for the great example.

Unknown said...

Yes, I am a Haskell newbie trying to explore the language through Real World Haskell. Most of the examples in the book are truly helpful. However, I found the example of the State monad slightly opaque mainly because of the fact that I am not (yet) familiar with the various classes like Random, RandomGen, StdGen etc. And I did not want to do a depth first exploration of those topics while I am trying to understand something else. OTOH fizzbuzz is a problem which can be suitably molded to demonstrate various idioms of the language.

Arnar Birgisson said...

By mapM_ing your collect function over the state monad, you are doing similar things to what the Writer monad does directly.

import Control.Monad.Writer

fizzbuzz n
| n `rem` 3 == 0 && n `rem` 5 == 0 = "fizzbuzz"
| n `rem` 3 == 0 = "fizz"
| n `rem` 5 == 0 = "buzz"
| otherwise = show n

fizzbuzzW :: Integer -> Writer [String] ()
fizzbuzzW = tell . return . fizzbuzz

main = print $ snd . runWriter $ mapM_ fizzbuzzW [1..100]

(please fix the indentation if blogger messes it up)

Anonymous said...

But why would you do that instead of just using IO directly? Like this:

main = sequence_ $ map (putStrLn . fizzbuzz) [1..100]

Mind you, I think your example is a good demonstration of how State works; but it'd be nice to see something that explains why to use it.

Unknown said...

@Arnar Birgisson:

Thanks for the input. I was trying to understand State monad with that example and had not yet gone through the Writer monad. Now, after going through the Writer monad, I discovered the same solution that u have mentioned. This, I guess, is the power of Haskell, that u can address every problem in multiple ways, but choose the solution which feels most succinct and elegant.

Arnar Birgisson said...

Actually, here's one silly way of fizzubzzing in the state monad:

import Control.Monad.State

next :: State (Int,Int,Int) String
next = do (a,b,c) <- get
put ((a+1) `mod` 3, (b+1) `mod` 5, c+1)
return $ case (a,b) of
(0,0) -> "fizzbuzz"
(0,_) -> "fizz"
(_,0) -> "buzz"
_ -> show c

main = print . take 100 . fst $ runState (sequence $ repeat next) (1,1,1)

Anonymous said...

instead of

(_, state) = runState ...

you can use the execState function

-- runState :: State s a -> s -> (a, s)
-- execState :: State s a -> s -> s

state = execState ...