Sunday, April 14, 2013

Amazing Mouse (Squeak the First)

You should have an essentially blank Haskell module that compiles and runs successfully.

We are now ready to begin adding definitions to the "Main.hs" source file to solve the maze and have our virtual mouse navigate its way to the pile of equally virtual cheese that lies beyond the exit.

I'm going to cheat a little by asking you to copy a bunch of import directives into the module to begin with.  Of course, usually you add imports as needed as you go along, but there are very few we'll need and this isn't a tutorial explaining how to find functions in Haskell libraries, so we'll just go ahead and add most of what we'll need now:

import Data.List
import Data.Maybe
import System.IO
import Control.Monad (guard, forM_)
import GHC.Exts

In general, it's a good idea to declare the names of individual dependencies in import directives.  That's because similar names are exported by multiple libraries and you'll have to decide which symbols you want to use unqualified and which you will qualify.  This is similar to most other languages you may have come across.  This program is so small that we won't bother with explicitly listing functions much. I've only specifically listed the two functions we need from the Control.Monad module.  

Now we can concentrate on the real business!

Indeed, the first order of business is to come up with a representation of mazes, i.e. a way to specify specific mazes that our program will solve.  

It's often valuable to prototype your data in any language.  It keeps things concrete and provides an early way to test ideas and the emerging code/logic.  In a 'value oriented' language like Haskell this seems even more true.  So, let's start by finding a nice simple representation of a maze.

So, what do we have to represent in order to define a maze?  Well, as described in the introduction, we need to represent a simple grid-like maze, where every coordinate/cell can be a empty space, a wall or one of two special spaces: the start and the exit.  When it comes to describing grid/table like things, we could use a matrix type, but usually we use a 'vector or vectors' (e.g. an array or arrays or list of lists).  There's a certain convenience in using ASCII strings to represent the contents of our maze, so we'll choose to using Strings to represent the X dimension of the maze with each character being a maze location in a 'column', and we'll have a List of these to represent the Y dimension (rows).

It turns out that Haskell's fundamental String type is represented as a list of characters.  Lists in Haskell are introduced with square brackets (both to construct list values and to express the list type).  So, the type of a string in Haskell can be written:
(... a list containing values of type 'Char', i.e. character).
Haskell also defines the type synonym "String" to mean this same type, for convenience.

So, with the concept of a maze being a List of rows, where each row is a String, we can define an encoding of the four location types as characters:
  • Empty will be a space ' '
  • Wall will be a asterisk '*'
  • Start will be an 'S'
  • Exit will be an 'X'
We can now define our first maze with strings and a list and give it a name:

charMaze0 =
    "*     *     *   X",
    "* **  ** *  **  *",
    "* *  **  * **  **",
    "*   *** ** *  ***",
    "*S* * *  * *    *",
    "*   *    * * *  *",
    "** ** **** * ****",
    "*      *        *",

The name is of course essentially irrelevant.  It has to conform to Haskell's identifier rules.
Note how in Haskell syntax this looks exactly like a definitions of a function with no arguments... and that's because this is exactly what a simple value is!  Values are functions without arguments, functions are values with arguments.  It's all functions in Haskell :-)

The definition of charMaze0 is formatted of course to present the geometry of the maze we're representing, but it's fairly easy to see that this is a list (note the enclosing square brackets) of strings separated by commas.  If we had been making a short list of counting numbers up to ten, then the constructor syntax would have been:  [1,2,3,4,5,6,7,8,9,10].

So, I think you would agree that this is a simple way for a human to represent new mazes for our program.  However, it's arguably not the best way to represent the maze in the program.  At the very least it would be nicer not to have to compare these special characters to determine their meaning.  So, instead we'll convert this 'character maze' representation to a 'material maze' representation where each location can have the value of only one of the four allowed materials: Empty, Wall, Start or Exit.

To begin with, we want to define a type that restricts its values to being one of the four legal material types.  Essentially we need an enumeration data type.  This is easy to define in Haskell:
data Material = Empty | Wall | Start | Exit

That definition reserves the new type name "Material" with four data constructor names "Empty", "Wall", "Start" and "Exit".  Any time we use the symbol "Start" in the code for example, the compiler will know that this is a precise discrete value of the type "Material".  

Now, while that's completely sufficient to define the new type of data for our discrete Material types, in fact we'll want to do some standard things with these values:
  • We'll want to test them for equality using the '==' operator  (e.g. myMaterial == Empty)
  • We may want to order or sort them 
  • We may want to automatically map them to cardinal indices (0->Empty, 1->Wall, 2->Start...)
  • We'll want to be able to render them as strings for printing like 'toString()' in Java
In Haskell, you can associate the ability for defined classes of functions and operators of a Type Class to work over new data types by making the data type an Instance of the Type Class.  I'm not going to describe this in detail in this worked example, but suffice it to say that:
  • The functions that determine equality (e.g. the "==" operator) are defined in the Eq Type Class
  • The functions that order values are defined in the Ord Type Class
  • The functions that map values onto (and from) counting numbers are defined in Enum
  • The functions that render values to strings are defined in the Show Type Class
Suffice it also to say that Haskell is able to magically add the necessary code to make a new data type a member of many of the common Type Classes, through the use of the "deriving" keyword in a data declaration.

Consequently, we can 'power up' our Material data declaration by appending a deriving clause, like this:
data Material = Empty | Wall | Start | Exit deriving (Eq, Ord, Enum, Show)

It is extremely common to derive Eq, Ord and Show on new data types, and you'll probably do this as a matter of course.  Enum is more unusual, but we're about to make use of the ability it endows to map between the character representation of a maze location and its Material.

Having just made an ordered enumeration of Material values, we can also define the ordered list (string) of characters that represent each in turn:
materialChars = " *SX"
The first character is space, representing "Empty", then '*' for Wall, then 'S'... etc.

If we had a function that mapped a character in this string to the material at the same position in the enumeration of Materials, then we'd be able to transform each maze position to its material.  

The function we need to produce takes a Char and returns a Material.  We can write out this contract right away as the type expression for a new function 'charToMaterial':
charToMaterial :: Char -> Material
Note, this is just a declaration of the type of charToMaterial that we've yet to write, but it introduces the type notation.  The "::" is syntax meaning "has the type", and the "->" syntax means "function".
So, overall, this type declaration says "charToMaterial is a function that takes a Char value and returns a Material value".

Type declarations in Haskell are usually optional.   However, it's a good idea to use them on top-level functions in your program.  Not only do they act as a useful annotation to convey intent and help comprehension, but they also let the compiler help you find coding errors more quickly.  If the compiler disagrees with want you've specified then it will tell you (an error), if it thinks you're being more picky about the type, but otherwise agrees (i.e. the actual type is more general), then it will adopt your more restrictive declaration.

So... to our definition of the charToMaterial function.
To obtain a mapping between these sequences we'll first look up the position index of the character in the materialChars string, then we'll obtain the value in the Material enumeration that pertains to this position.  

We'll use a couple of library functions for this purpose.  Here are their types and some discussion:

elemIndex :: Eq a => a -> [a] -> Maybe Int
elemIndex is a function that takes a value a and some list of as and return a "Maybe Int".
Note how Haskell represents multiple arguments as types separated by the "->" function symbol.  Without going into the whys and wherefores (and ignoring the Eq a => bit), this can be read as "elemIndex" is a function that takes an "a", that when applied to that argument, returns a function that takes an "[a]" and returns a Maybe Int.  As we shall see, Haskell does indeed let you apply less that the formal arguments of a function in order to return another function that takes the remaining arguments.
We'll use this function to look up a single character (an 'a') in a list of characters (a String) to obtain the index of the character.  
What's that strange "Eq a =>" stuff?  It means that all following 'a' must belong to the Eq Type Class.
In our use case we want 'a' to be a Char, which is certainly already a member of 'Eq'.
What's that strange "Maybe Int"?  Well, it's possible that the given character doesn't appear in the given string at all!  So what should our index function return?  In some languages like C, a similar function would return a value like -1.  The special case is indistinguishable in type from the normal indexes, which is less than ideal.  Some languages might return some kind of 'null' in this case, but that's error prone too.  Haskell has a way to make a kind of type-safe null for any other type - it's called the Maybe type.  In this case the result will either be a value like "Nothing" (no index), or "Just 1" (the index was found and it's the integer "1").  

fromMaybe :: a -> Maybe a -> a
fromMaybe is a function that will help us manage the "Maybe Int" that will be returned from elemIndex.  It's only purpose is to look at a given Maybe value (Maybe a) and either return the "Just" value (e.g. the 1 index in the above example for elemIndex) or some placeholder value 'a' if the Maybe value is Nothing.  
We will use this function to simply extract the index if one is available, or raise an appropriate error if we were unable to determine the index of a character.

error :: [Char] -> a
error is a function that raises an exception in the running program with a given error message (the [Char]).  We will use this to signal that the desired maze location character was not found (no index).

toEnum :: Int -> a
toEnum returns the value of an enumeration for some given index.  The data type it returns must belong to the Enum Type Class.
We'll use this function to obtain the appropriate value of a Material from the index of the character in the maze characters string.

So, finally, here's our definition of the charToMaterial function:
charToMaterial char = toEnum index
        index = fromMaybe (error $ "Invalid material character: " ++ show char) $ 
                     elemIndex char materialChars

Putting this all together, we can see that charToMaterial returns some enumeration value pertaining to the given index.  The value of index is defined as a local definition of this function (Haskell provides a "where" keyword to introduce local definitions and also a "" expression to do something similar).  
To determine the index, we first use 'elemIndex' with the character we're given and the "materialChars" string.  This will return in the Maybe Int value that we then analyse with "fromMaybe".  If the value is "Nothing", then the first argument of fromMaybe is the result - in this case an error explaining the problem.  If the Maybe Int value contains an actual index, then this becomes the value of "index".  Note that the "$" operators simply mean "do everything to the right and then feed the result into an argument in the expression on the left".  "$" is used to avoid using more parentheses in expressions.

There's a small piece of Haskell magic in play in this definition.  How does toEnum know which enumeration type to return a value for?  Well, that's determined by the type context.  In this case we've already provided a type for the charToMaterial function, with the return type "Material".  However, if we hadn't provided this type declaration then Haskell would have determined that charToMaterial was polymorphic in its return type.  That would have meant that the function could have been used in contexts with different enumerations.

Once you have a function to transform an element, you always have a way to transform a list of elements via Haskell's map function.  The map function has the following type:
map :: (a -> b) -> [a] -> [b]

This is a function whose first argument (a->b) is itself a function from a to b.  The second argument is a list of 'a' and the result is a list of 'b'.  In fact map is defined to apply the (a->b) function to every element in the second argument in order to get the resulting list.

To convert all the characters in our textual maze (which is in fact a list of lists of characters), we need to apply two levels of mapping.  An inner map (applied to each row/string) must map every character to a Material using charToMaterial.  Then the function that does this mapping must be mapped over every row of the maze.
The inner map (converting characters in rows) could be written like this:
rowMap row = map charToMaterial row

The outer map could then be written like this:
mazeMap maze = map (rowMap) maze

However, there's no need to name the rowMap function, we can just pass it into the mazeMap's map by converting it to an anonymous function (also called a lambda function).  Lambdas are way to create a function value in the middle on an expression, rather than as a named definition.  Instead of a name, they start with a backslash (\) and instead of an = before the definition, you use an arrow (->).  So, the lambda version of rowMap is:
\row -> map charToMaterial row
and the mazeMap function could then be written:
mazeMap maze = map (\row -> map charToMaterial row) maze

This definition is adequate, but believe it or not it's not as concise as we can be with Haskell - if we want to be.  We have argument names (maze, row) that might be useful annotation in the program to assist readability, but they are both unnecessary.  Because of the fact mentioned earlier that you can miss out trailing arguments when applying functions to arguments (to get an anonymous function), you can use this technique to generate the functions passed to map.  This is called partial application.

To illustrate partial application, let's say I have the library function "take", which takes the first n elements of a list.  Its type is:
take :: Int -> [a] -> [a]

If I only apply take in its first argument, this effectively removes the first argument in the type definition, leaving the rest as the type of the result.  The grey part of the type disappears...
Int -> [a] -> [a]

So if I define:
firstTenFromList = take 10

firstTenFromList must have the type [a] -> [a], and indeed it represents the function that if you provide a list, will always return the first 10 elements.

Now, in this case I have assigned a name to the resulting, otherwise anonymous, function.  However I don't have to do this in the context of application.  Consequently, I could write the mazeMap function as:
mazeMap maze = map (map charToMaterial) maze

This works because map with only its first argument applied results in the type [a] -> [b], which itself is a perfectly good transforming function to apply to another map.

Notice that I can apply the same trick to the outer level "maze" argument in this definition too.  The 'maze' argument is only being applied as the last argument at the top level, so it can be elided in the definition too.  If we do this, we arrive at the most concise definition:
mazeMap = map (map charToMaterial)

This is known as the points-free style (points being the named arguments).  Whether you consider this as readable as the version with the extra argument names is entirely subjective.  In all likelihood, when you are starting out with Haskell you will probably want to leave the extra names in.  However, partial application itself is a very powerful way to generate new functions by specializing existing definitions.

Let's give a type definition to our mazeMap function (especially important if you have a points-free definition).
This map converts a character based maze whose value has the type [[Char]] (or [String] if you prefer) to a Materials based maze whose value has the type [[Material]].  The two levels of list are a bit of an eyesore, and we'll be wanting to refer to these types a lot.  Luckily Haskell provides a way to give a simpler name to a more complex type expression.
We can define a nice alias for the character type maze by declaring:
type CharMaze = [String]
and similarly for the Material maze:
type Maze = [[Material]]

Now we can declare the type of mazeMap on the line before its definition as:
mazeMap :: CharMaze -> Maze

We now have our maze expressed in a useful form for processing by our program.
We'll need a few utility functions to access various properties of the maze:
  1. What the Material is at a given (x,y) location in the maze
  2. The overall size of the maze (width, height)
  3. The location of the special exit and start locations in the maze
In the remainder of this post, we'll define these functions.  We'll get to the business of navigating the maze in the next post.

1. Finding the Material at a given location in the maze
We'll need this function when the mouse needs to 'look around' its current position and ascertain what moves are available to it.
We can specify the type easily enough (I'll keep separate x and y arguments for the location):
materialAt :: Maze -> Int -> Int -> Material

Really, all we need to do for this is lookup the correct row in the outer list (indexed by y) and then lookup the correct location in the inner list/row (indexed by x).  It turns out that Haskell's standard list library has a list index operator (!!) that does exactly this.  So, we just have to use a pair of those:
materialAt maze x y = (maze !! y) !! x

2. Determining the overall size of a maze
We'll want to return two values from this function: the width of the maze (along x) and the height (up y).  A way to pass informal collections of values in Haskell (as arguments or results) is to use a tuple.  

A tuple is a container holding a fixed number of values, which can each have an independent type.  All tuples are constructed with parentheses and comma separated values.  There's a 2-tuple, sometimes called a Pair e.g. (1,"Fred"), and a 3-tuple/triple e.g. ('a', "Hello", 25.7), a 4-tuple, etc...
There's even a special 0-tuple, expressed with empty parentheses ().  This is more useful than it seems as it is a singleton value - it always results in the same value when constructed and it can carry no useful informational payload.  Because of its singleton nature it is called "unit".

We can construct tuples with expressions in the value positions e.g. (2 + 3, "h" ++ "ello) so we just need to figure out the expressions for the width of the maze and the height of the maze, then return the pair value (<width expr>, <height expr>).

The height of the maze is easy, this is just the number of rows in the outer list.  The standard library function for obtaining the length of a list is the er... length function.  Getting the width of the maze is a little harder.  Nothing is preventing us from having different sized rows, at the moment at least.  However we will assume that a well-formed maze has all its rows of equal length, and we'll just return the length of the first row.  To get the first item of a list there's a standard function head.  We'll use this to get the first row of the maze, then use length again to get that row's width.   Putting this all together we can define a function:
mazeSize maze = (length $ head maze, length maze)
Once again, the '$' operator just saves an extra pair of parentheses.  It forces "head maze" to be evaluated before the result is provided to length.

3. Determining the location of the start and exit locations in the maze
This is the last function to define in this post and it will introduce another nice feature of Haskell: list comprehensions, so we'll bow out with style.

Finding the start or exit location is really the same function - being a function that searches the maze (lists) for a location with a particular Material (e.g. Start or Exit).   While this won't be particularly efficient, we've already defined a materialAt function, so we'll just use that to look up the Material at a given location and compare it with the Material we're looking for.  We just have to generate all the x and y locations in the maze and use these to produce the list of all (x, y) locations that have the Material we want - in fact we'll just take the first one encountered seeing as there's only supposed to be exactly one Start and one Exit.  We're OK with a little inefficiency, because we'll only use this function once when running the program to ascertain these two locations.

So, if we're going to generate x and y locations to generate a list of locations that meet the requirement of matching a Material we're looking for, then as noted a list comprehension is a good tool.  A list comprehension lets you generate and combine lists in order to generate more lists.  Given that lists represent any kind of sequence in Haskell, this is a very powerful way to build value generators.  

Here's the algorithm to return a list of locations with the Material we're looking for:
  • Determine the extents (size) of the given maze
  • Generate all the y coords in the maze from 0 to height -1 
  • Generate all the x coords in the maze from 0 to width - 1
  • Keep any x and y where the materialAt x y is equal to the Material we're looking for 
  • Return this (x,y) pair
We'll call this function "allMatchingLocs"

As mentioned, we only really care about the first instance of a location with the Material being searched for, so we'll define a top-level function "firstLocation" to simply return the first item in the list of (x,y) pairs returned by allMatchingLocs.  

Here's the requisite definitions, which we'll unpack a bit below:
firstLocation mat maze = head allMatchingLocs
        allMatchingLocs = [(x,y) | let (mazeWidth, mazeHeight) = mazeSize maze,
            y <- [0 .. mazeHeight - 1], x <- [0 .. mazeWidth - 1],
            materialAt maze x y == mat

firstLocation has two formal arguments "mat" which is the value of the Material we're looking for (e.g. Start), and "maze" which is the maze to search.  All the outer definition of this function does is return the first element (head) of allMatchingLocs, being a local function definition after a "where".  The allMatchingLocs function is where all the action is of course and this is where we meet the new list comprehension syntax.  List comprehensions are delimited by square brackets, in effect saying "a list is being constructed".  However, inside the brackets are all sorts of expressions.  In fact the syntax is relatively straightforward.  The first part, up to the vertical bar contains the constructor for each value to be returned in the list - in this case we want pairs of (x,y) coords.  After the vertical bar come a series of expressions separated by commas that can bind names in various ways for following expressions, or filter possible values for bound names.  The latest versions of Haskell also allow sorting and grouping of values (much like SQL), but we're not using these features here.  

The clauses that occur in our list comprehension are exactly the bulleted steps outlined earlier.  
First, we use mazeSize to get the width and height pair for the maze.  Note that we use another cool feature of Haskell, pattern matching, to assign names to both values inside the pair directly.  This will result in "mazeWidth" being the width of the maze and "mazeHeight" being the height.  
Having bound those names to the extent values, we can use them to generate the actual coords to test.  

The y <- [0 .. mazeHeight -1] clause associates the name "y" with each value in the set (list) of height coords.  This is another list generator inside the list comprehension, in this case it uses the range operator (..) to generate values between 0 and one less than the height as you'd expect.
Note that the syntax <- is reminiscent of the 'element of' (∈) set operator in maths, but in any case, you can think of it as being like a 'for' loop in your favourite imperative language.

Having established the y's we do the same for the x's in a very similar way (bound by the width of course).  

The next line does the real work, it is a predicate that selects for only x y pairs that meet acceptance criteria.  In this case the Material at that location in the maze most be the same as the Material we're looking for.  Note that we're using == here, naturally, but this would only work if values of Material are testable for equality by being in the Eq Type Class.  Luckily, we made sure of that by deriving "Eq" on the Material data type definition.

In a list comprehension, any time that bound values reach the end of the list of clauses, they can generate a new value in the resulting list.  Thus, for every x and y pair that pass the material test, the x and y values will be used in the value constructor (before the vertical bar of the list comprehension) to build a new list value.  In this case we build them into pair (x,y).

Now, I mentioned inefficiencies earlier.  These actually pertain to the use of repeated index lookups in lists via the materialAt function that uses !!.  For small mazes this won't be a problem, but for larger mazes it would be much more efficient to traverse the list structure itself once, keeping a record of x and y indices, but looking for the required material as we go.  Lists are not random access structures and the way that firstLocation currently works by permuting indexes and then 'subscripting' the lists in the maze is poor form.  Nevertheless, one seeming inefficiency about the current definition is interesting to discuss. 

The way firstLocation is written looks like it runs the entire allMatchingLocs logic to completion, before simply taking the first element of this list.  This seeming bit of extravagance is in fact beautifully and automatically optimised by Haskell's lazy evaluation.  Because definitions are only evaluated when they are required to produce a value, firstLocation's use of head will cause allMatchingLocs to evaluate only until it produces the first value.  After this, all the definition of allMatchingLocs and all its runtime overhead will be deleted as there is no way it can ever be required to produce another value. The upshot of that is that allMatchingLocs will only ever explore as much of the maze as is needed to find the first matching location (despite its name), because that is all that is required of its single consumer.  In Haskell generators and list processors like allMatchingLocs can quite happily express infinite sequences of computation.  As long as some consumer doesn't attempt to read all of the infinite list at once, then this can result in very elegant ways to express logic and glue processes together.

Having created the general firstLocation search function for a particular material, it's a simple matter to specialise it for the two special locations we'll need to find: the Start and Exit.  Again, we'll use partial application to create new functions from the general firstLocation function and we'll give these new functions appropriate names:

exitLocation = firstLocation Exit
startLocation = firstLocation Start

Note that this works easily because we arranged for firstLocation to have the Material value we're searching for as its first argument.  This motivates a good tip: when designing a function it's a good idea to think about specialisation by partial application when you're designing the argument order.    

So, that's it for this episode.  We've built a way to represent mazes and to obtain various important properties of a given maze.  In the next post we'll teach our virtual mouse how to determine what directions it can move in, how to sniff out the exit and then get it exploring paths to the Exit from its Start location.

No comments:

Post a Comment