Daniel's Blog

edit

Haskell Arrows

Posted by Daniel Lyons Sun, 08 Apr 2007 11:14:00 GMT

Just a quick post about my implementation of FizzBuzz with Arrows.

If you’re not familiar with arrows, they’re usually called a generalization of monads to arbitrary computations. In this case I realized I could use an arrow to handle the combination of both mod 3 and mod 5 tests. In reality, it isn’t much nicer than the ordinary function composition method, except that I get to write the tricky part in points-free form. Actually, most of the program is points-free.

The usual stuff at the beginning, and the Arrow library:

module Main where
import Control.Arrow

For simplicity, I defined some helper functions for testing divisibility and generating a test. I decided to use the Either monad to carry around either an integer if the function didn’t mangle the number into a string, or the string. Then I use the utility to define my functions three and five which handle their respective tests:

-- True if y divides x evenly
divides :: (Integral a) => a -> a -> Bool
x `divides` y  =  y `mod` x == 0

-- Generates an Either monad function for two types
genTest :: (a -> Bool) -> b -> a -> Either a b
genTest test result x = if test x then Right result else Left x

-- The fizzbuzz functions
three, five :: Integer -> Either Integer String
three = genTest (divides 3) "Fizz" 
five  = genTest (divides 5) "Buzz" 

The last piece of the FizzBuzz part of the problem is something which combines the result of the three and five functions. I wish there were a way to get rid of this but I’m not sure there is. At least by using pattern matching, I think the code is somewhat more aesthetically pleasing. Take a look:

-- A thing to combine the results of the fizzbuzz functions
combine :: Either Integer String -> Either Integer String -> String
combine (Left x)  (Left _)  = show x
combine (Right x) (Right y) = x ++ y
combine (Right x) _ = x
combine _ (Right y) = y

OK, just one thing left: actually sequencing the operations and doing the damn work! I want to wind up with a function which takes a number and returns the appropriate string:

-- OK, run three and five with the same input and combine the result
fizzbuzzArrow :: Integer -> String
fizzbuzzArrow = three &&& five >>> uncurry combine

This is the real meat. The arrow here is doing this computation (forgive my horrible ASCII art:

          val
           |
           |
           |
         (&&&) -- the fanout operator copies val
          / \
         /   \
        /     \
       /       \ 
      /         \
     |           |
     |           |
    three val    |    -- call three on the first copy
     |           |
     |      five val  -- call five on the second copy
     |           |
     |   (>>>)   |    -- send both values onward
     |           |
    (r1,        r2)   -- if r1 = three val and
     |           |       r2 = five val, this is the 
     |           |       tuple we're carrying around
     |          /
     |         /
     |        /
     |       /
     |      /
     |     /
    uncurry combine   -- uncurry unpacks a 2-tuple into
           |             two args for a function call
           |             thereby calling our "combine" 
           |
        result        -- this is the function's result 

I hope that’s clear!

Now that we have our fizzbuzzArrow function which takes a number and produces the right string, we just have to call it on the correct input and print out the result. This is pretty simple in Haskell:

-- The main: apply the function (with printing with a newline) to all of
-- the first hundred integers.
main = mapM_ (putStrLn . fizzbuzzArrow) [1..100]

Nothing tricky there; just using mapM_ to send the list of numbers between 1 and 100 through a function composition of putStrLn and fizzbuzzArrow. The composition has type Integer -> IO (), which is why mapM_ is necessary rather than map.

All this, just for points-free style?! How about the simpler, non-arrow function combining method! It looks almost the same:

-- fizzbuzz :: Integer -> String
fizzbuzz x = uncurry combine (three x, five x)

main = mapM_ (putStrLn . fizzbuzz) [1..100]

Yeah, yeah… well, hopefully the arrow is at least instructional!