Chessguy pointed out that it's currently hard to play along with the monad wars code.

It would be nice for the posts to be “literate haskell”, where sections preceded by “>“ characters are valid Haskell. The idea is great - that you can mix sections of introduction and description with sections of actual code, ending up with an article that is also executable code! Which is very much the style of these posts, but right now I'm being too lazy to go that extra step:

• sometimes I show multiple version of the same function, (some of them might not work)
• I tend to introduce imports as needed but (I believe) they need to be at the top of the file
• I don't always repeat functions from earlier posts but just refer to them

So I've posted the current source to my subversion repo. As you can see they're currently related to the number of the associated post, and contain different areas of functionality: this is actually how I'm working on it for the moment - I'm hoping to put together some of the pieces in part 5 or so (Blog Driven Development is a rather odd way to structure your work but there you go...)

Update: Vincenz on #haskell convinced me that I really should try literate haskell - watch this space...

I'm now probably going to fall off the internet for a week while I move country and job.  I'll be at the London Perl Workshop this Saturday and will talk (for a whole 5 minutes!) about Monad Wars. Maybe see you there :D

One of the advantages of demonstrating your ignorance in public is that you may receive useful corrections... thanks to everyone who replied on these recent posts, I found the comments very instructive, and thought it was worth writing up as a new post.

Strict records

ddarius got in touch to mention that I might want to use “strict fields”. This might be an issue if I'm incrementing, say, turn, but not actually using the value. I'd end up building up a “thunk” (an unevaluated expression) like 1+1+1+1+1+1+1, which will get evaluated later (and if too much later, it could cause some problems like stack overflow). Actually, I don't think this will happen in this particular case (I'll be printing the turn count every time) but it's not hard to implement (just need to put a “!” before the strict fields)

 > data GameState = GameState {
 >        turn     :: !Integer,
 >        score    :: Integer,
 >        location :: Location
 >    } deriving Show

Also, as nominolo suggested, in conjunction with -funbox-strict-fields, it can open up some possible optimizations.

Not Just Maybe

Now this is an interesting one. I was whining in my last post about Data.Map.lookup

but which monad is it in, and more to the point, why?

As you might imagine, I really wasn't getting it... and the code I wrote around it rather reflects that...

Vincenz, Rich Neswold, and “rm” all pointed out in rapid succession that the function I'd created for parseMap was completely redundant. Here, for comparison, is my first version.

 > parseMap m s | M.member s m = do v <- M.lookup s m
 >                                  Just v
 >              | otherwise    = Nothing

I wrote this because, from the ghci command line, it looked like M.lookup threw an error if it couldn't find the key. The suggestion, which is rather briefer is as follows:

 > parseMap = flip M.lookup

The flip is only there because parseMap and Data.Map.lookup take their arguments in opposite orders. Otherwise lookup and parseMap are identical!

But how does this return a “Just” or a “Nothing” appropriately? Apparently, on success, it returns a Monad of the appropriate type by default. If on the other hand it doesn't work, it will fail.

The IO monad maps a fail to an error (which is why I saw the exception I mentioned in the post!) But Maybe will map it to Nothing.

So from the ghci command line, we can create a small test Data.Map and run some lookups against it “in” various monads.

 Prelude Data.Map> let m = Data.Map.fromList ("one", 1)

 -- success
 Prelude Data.Map> Data.Map.lookup "one" m  :: Maybe String
 Just "uno"

 Prelude Data.Map> Data.Map.lookup "one" m  :: [String]
 ["uno"]

 Prelude Data.Map> Data.Map.lookup "one" m  :: IO String
 "uno"

 -- fail
 Prelude Data.Map> Data.Map.lookup "two" m  :: Maybe String
 Nothing

 Prelude Data.Map> Data.Map.lookup "two" m  :: [String]
 []

 Prelude Data.Map> Data.Map.lookup "two" m  :: IO String
 *** Exception: user error (Data.Map.lookup: Key not found)

ddarius gave a name to this technique, “Not Just Maybe”. That is, if you were going to write a function that returns Maybe “Just 1“ and Maybe “Nothing”, then you might as well just write it as a generic monad. This will then be usable within Maybe, as planned, but also in IO and List too.

This sparked an interesting discussion about “Common Idioms” in Haskell. Apparently the pages that used to exist on this topic haven't yet been migrated to the new wiki. But there are some notes, for example on this snapshot of the NotJustMaybe page.

ddarius also suggested I could rewrite parseInt similarly

 > import Control.Monad
 >
 > parseInt :: MonadPlus m => String -> m Int
 > parseInt s | all isDigit s = return $ read s
 >            | otherwise     = mzero

Using MonadPlus, 1) requires the Control.Monad import. 2) seems to require the type signature. 3) it looks like IO doesn't have an mzero, so you can't now type

 *Main> parseInt "4" 
 <interactive>:1:0:
    Ambiguous type variable `m' in the constraint:
      `MonadPlus m'

at the command line and have it Do The Right Thing. I'd read that fail is considered bad style (for some reason), but it seems to be rather more convenient on these 3 counts at least:

 > -- type will be inferred if omitted
 > parseInt :: Monad m => String -> m Int
 > parseInt s | all isDigit s = return $ read s
 >            | otherwise     = fail "not an int"

This time around, we're going to look at how we'll turn user input into commands in Monad Wars.

I think that the easiest option to implement will also be very convenient to play with: a command line where we issue commands like:

    $ buy 4 foo
    $ sell 20  bar
    $ jet bronx

or with abbreviations

    $ b 4 f

and where it's unambiguous, collapse spaces:

    $ b4f

Tokenising

We'll start by tokenising the command line string. This is almost as easy as using the Prelude function words. The only complication is that we want to tokenise alternate letters and numbers separately, like the “b4f” example above.

We'll use groupBy from Data.List, and isLetter from Data.Char.

 > import Data.List
 > import Data.Char
 >
 > tokenizeLine :: [Char] -> [[Char]]
 > tokenizeLine = concatMap 
 >                   (groupBy ((==) `on` isLetter)) 
 >                   . words

Annoyingly, on (in the Prelude in GHC 6.8) doesn't exist in my 6.6.1 installation, so we'll have to define it:

 > op `on` p = (\a b -> p a `op` p b)

Let's just see how groupBy works:

 *Main> groupBy (==) "aabbbcdd"
 ["aa","bbb","c","dd"]

 *Main> groupBy (\a b -> isLetter a == isLetter b) "abc123def"
 ["abc","123","def"]

The on expression is a nicer way of writing the second case. We then map this grouping over each of the tokens, getting our final list.

 *Main> tokenizeLine "jet quuxville"
 ["jet","quuxville"]
 *Main> tokenizeLine "b3p"
 ["b","3","p"]

Parsing

Now we'll want to do things with the tokens. Yes, there are libraries to do this (Parsec etc.) I know that in the Perl world I'd often tell other people not to reinvent the wheel and to use CPAN, so I do feel a little naughty that I'm going to ignore these and handroll something myself. In my defence m'ludd,

• I'm only parsing very simple commands
• Learning a new library requires cognitive effort. I have limited time for this task, and I believe (possibly wrongly) that I will be able to “roll my own” more quickly.
• Reimplementing functionality can be instructive in and of itself
• It also makes you appreciate how simple the “official” solution really is, when you finally get around to learning it.

In an expression like buy 4 foo I'm imagining that “buy” will map to some command. Then we'll need to parse “4“ as a number, and “foo” as a some merchandise. The first case is the simplest:

 > parseInt :: String -> Maybe Int
 > parseInt s | all isDigit s = Just $ read s
 >            | otherwise     = Nothing

This reads tantalisingly close to English: If all the string is made up of digits, we just read it as an Integer. Otherwise we return nothing. OK, I'm glossing rather over the “Just” and “Nothing” which indicate whether the parse succeeded using the “Maybe” monad.

 *Main> parseInt "42"
 Just 42
 *Main> parseInt "wibble"
 Nothing

Now for parsing the merchandise: if there is an item called “foo”, we'd want to match “foo”, “fo”, “f”. By amazing coincidence, I recently wrote about a function that does exactly what we need:

 > import qualified Data.Map as M
 > import Control.Arrow

 > getPrefixes :: [([a], t)] -> [([a], t)]
 > getPrefixes = concatMap $ uncurry zip . 
 >                  (tail . inits . fst &&& repeat . snd)

 > getPrefixMap :: (Ord a) => [([a], t)] -> M.Map [a] t
 > getPrefixMap = M.fromList . getPrefixes

So we'd need a list of merchandise. Which means we should think a little about what the datatype will look like. I'm going with a record type again, because I know there is more information that we'll need to store:

 > data Merchandise = Merchandise {
 >                  name :: String,
 >                  min  :: Int,    -- minimum price
 >                  max  :: Int     -- maximum price
 >                }
 >    deriving Show

Next, we define the products on offer, by looking at the Dope Wars configuration pages, we can copy the prices, but of course we have to theme the names...

 > merchandise :: [Merchandise]
 > merchandise = [
 >    Merchandise "Arrows"  1000  4400,
 >    Merchandise "Curry"   15000 29000,
 >    Merchandise "Kleisli" 480   1280,
 >    Merchandise "Haskell" 5500  13000,
 >    Merchandise "Lambdas" 11    60,
 >    Merchandise "STM"     1500  4400,
 >    Merchandise "Monads"  540   1250,
 >    Merchandise "GHC"     1000  2500,
 >    Merchandise "Peyton"  220   700,
 >    Merchandise "Fundeps" 630   1300,
 >    Merchandise "Zipper"  90    250,
 >    Merchandise "Endo"    315   890
 >    ]

Now this isn't in the form we need it yet. First of all, we'll map this list to a list of tuples of [(string, thing),...], which is exactly what getPrefixMap is expecting:

 > merchandiseMap = getPrefixMap $ 
 >                  map (\i -> (toLowerS $ name i, i))
 >                  merchandise

 > -- toLowerS over a string isn't defined by default, but it's just:
 > toLowerS = map toLower

OK, for a bit of fun, we could write the map as:

 >              -- map (toLowerS . name &&& id)

(I don't yet understand why “arrows” are supposed to be an “even more generic model of computation than monads”, but they're certainly good for putting things in tuples :-)

Now we can build the parser parseMerchandise. Or rather (as we'll probably use this technique again, for example for the names of locations, and even the commands like “buy” and “jet”), we'll create parseMap

Interestingly Data.Map's lookup function throws an exception (as a “user error”!) if you try to look up a key that doesn't exist. (This is rather different from Perl hashes, but it makes sense in a strongly typed language - there is no “undef” value which is of the requested type!) So that I can avoid having to learn exceptions just yet, I'm going to check first of all if the key exists using member

 > parseMap m s | M.member s m = do v <- M.lookup s m
 >                                  Just v
 >              | otherwise    = Nothing

I spent about half an hour trying to get the above to work. After a number of rather unhelpful error messages about monads, I changed from my original attempt v = M.lookup s m to the do-notation form. This is rather odd, as it implies that lookup is monadic. And its type does indeed suggest that the result is in some monad...

 *Main> :t M.lookup
 M.lookup :: (Ord k, Monad m) => k -> M.Map k a -> m a

but which monad is it in, and more to the point, why?

In any case, now it's easy as pie(*) to create our merchandise parser as a specialization of our general function:

 > parseMerchandise :: String -> Maybe Merchandise
 > parseMerchandise = parseMap merchandiseMap

and we can now recognize the names and abbreviations of elements in the list!

 *Main> parseMerchandise "pey"
 Just (Merchandise {name = "Peyton", min = 220, max = 700})
 *Main> parseMerchandise "vb"
 Nothing

Next time around, we'll create “buy” and “sell” handlers that parse the whole command line, and stub in the actual interaction with the game state!

(*) Well, I say easy, but at this point (and ongoing) we get bitten by the “monomorphism restriction”, whatever that is. The error message suggests that you add explicit types to all the functions involved, but when I try that, I regularly get even stranger error messages about rigid variables and monads. The easier solution seems to be to add -fno-monomorphism-restriction to your ghci call. (I don't know enough to know whether this is a Bad Thing). Of course, now this error message doesn't come up. Pah!

A lot of learning projects involve writing games: people have written clones of Tetris, Asteroids, Space Invaders, and even first person shooters (Frag) in Haskell. As I'm far less clever than these people, I thought I'd start with something a bit simpler: Dope Wars.

Dope Wars is basically a trading game. In 30 turns, you move from one location to another, buying and selling, er, drugs on the streets of New York. It's a fairly simple concept, but one which includes elements like:

• Input and Output
• Game state
• Random numbers

all of which seem like a good way to learn Monads and the other building blocks that you need to actually do anything useful in a functional programming language like Haskell.

So I had the idea, wrote up a couple of datatypes and some functions, and then forgot about it. Then, when Greg McCarroll mentioned that he'd accept talks about other languages for the London Perl Workshop on December 1st, I thought it would be a great opportunity to push myself to do it by proposing a lightning talk.

Only problem: I now have to actually write the game in order to talk about it (*). So... here goes. In this post, I'm going to show a first draft for the game prompt.

State

OK, people often find it most convenient to do State using “Monads”. I think I'm going to leave that for now, and just thread state explicitly. Mainly because I haven't yet got around to learning how to use the State Monad. Hopefully this will eventually become annoying enough that it will give me impetus to learn the monadic version.

Anyway, the idea here is that we'd have some function playTurn that will look a bit like this:

 > playTurn :: GameState -> IO ()
 > playTurn gs = let gs' = doSomething gs
 >               in  playTurn gs'

(There is an interesting post on haskell-cafe about a more sophisticated monadic representation of the prompt).

So we just need to work out how to represent this GameState object. To start off with, we'll want to store information like

• Which turn it is
• What our score is (how much money we have)
• Where we are on the game map

We could create a normal tuple:

 > data GameState = GameState Integer Integer Location
 >                         -- turn    score   location

and then pattern match on this, but it's going to get horrible if we add any fields later on! In Perl I'd just use a hash, but remember that Haskell Data.Map objects map from one type to another, and we might well have values of various types.

When I asked on #haskell, dons and firefly told me about the record syntax:

 > data GameState = GameState {
 >        turn     :: Integer,
 >        score    :: Integer,
 >        location :: Location
 >    } deriving Show
 > 
 > -- for now:
 > type Location = Integer

Defining the original state is easy:

 > startState = GameState {
 >    turn     = 1,
 >    score    = 0,
 >    location = 0
 >  }

And to “modify” it (or rather to clone it, overriding certain fields) there is a convenient syntax that just lets us declare those fields which have changed:

 > movedToBronx = gs { location = bronx }

Setting a field to a value is easy, but we might want to define some mutators to change the field relative to its current value:

 > nextTurn :: GameState -> GameState
 > nextTurn gs = gs { turn = succ $ turn gs }
 >
 > modScore :: Integer -> GameState -> GameState
 > modScore d gs = gs { score = score gs + d }

The record syntax will work even when we inevitably add new fields later. Yay!

Prompt

Now, the game cycle is a bit more complicated than the version I suggested above, as it will allow IO actions in it. Something perhaps like this:

 > playTurn gs = do showStatus gs
 >                  putStr prompt
 >                  s <- getLine
 >                  let f = parseLine s
 >                  let gs' = f gs
 >                  if isEnd gs' 
 >                     then endGame  gs'
 >                     else playTurn gs'

For now we'll just stub some of the declarations we need. showStatus can just show the GameState record (which is why we derived the Show class).

 > showStatus gs = putStrLn $ show gs

We may as well set the prompt to the dollar sign, appropriately:

 > prompt   = "$ "

Though we'll need to parse the line read from standard input to one of the commands like “Buy 4 X” or “Goto location 3“, right now, we'll just stub in a function that increments the score and the turn counter:

 > parseLine s =   nextTurn 
 >               . modScore 10 

We need to know if we're at the end of the game, and take action appropriately.

 > isEnd gs = turn gs > maxTurns
 > 
 > maxTurns = 3
 > 
 > endGame gs = do putStrLn   "Game over!"
 >                 putStrLn $ "Your score was " ++ (show $ score gs)
 >                 return ()

And here's a transcript

 *Main> playTurn startState
 GameState {turn = 1, score = 10, location = 0}
 > buy  2 foo
 GameState {turn = 2, score = 20, location = 0}
 > sell 4 bar
 GameState {turn = 3, score = 30, location = 0}
 > goto quuxtown
 Game over!
 Your score was 40

(*) to be fair, it's only a 5 minute “Lightning Talk”, so I could probably get away without even writing the whole game, but I'll feel better if I actually know what I'm talking about...