Monad Wars – 2: the command line

. Leave a comment.

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!