Monday, April 29, 2013

Haskell Close Encounters (of the TUI and GUI kinds)

Most actual functional programs I've ever written have been 'engine' like things, not having any IO for attended operation per se.  That includes utilities and small apps that just use the command line for processing data and outputting results to the console or files.

Due to some prospective new projects, I have been wondering what sort of UI libraries might exist for Haskell and what the experience of writing UIs natively in Haskell might be.

My all-time favourite GUI framework is Apple's Cocoa environment.  I find this to be extremely powerful and (normally) easy to use.  Certainly, it is mature, with a strong/clean design.   It's also convenient and fast.  Unfortunately it is to all intents and purposes Mac only and there's no up-to-date, well maintained Haskell binding (I've found hoc, but that appears to be abandoned).  Although I don't spend any time in the Windows world any more, the situation there seems to be pretty fluid - but in any case the main UI frameworks there are again 'proprietary' and platform-specific.

Now, I can see value in two types of UI for various kinds of program I write:
  1. For simple applications and utilities, a pseudo-graphical terminal UI in the style of Midnight Commander can be very effective.  Moreover, these TUIs are potentially cross-platform and are very light-weight for use across networks.  While these TUIs aren't exactly common these days (I suppose they hearken too much back to DOS!), they are practically zero-client!  
  2. For more sophisticated applications, and of course where actual audio-visual media must be presented or edited, then a full GUI is required.
As I'm interested in both of these types of UI, I have taken to exploring the options of doing each with Haskell.  There are also web UIs of course, and Haskell does seem to have several very good frameworks for developing these (Yesod and Snap come to mind).  

TUI libraries in Haskell

I'm surprised we don't see more utilities and 'technical' apps provided with this first kind of UI.  I suspect this may be partly to do with the relative cost of creating TUIs with commonly available libraries, though it's probably also true that the set of apps that are appropriate for such treatment are a limited set and most people just reach for the GUI toolkits come what may.

If you have spent any time around Unix, then you'll know that there's a family of C libraries known as "curses" libraries available for building apps that do textual 'drawing' in a terminal/console.  These libraries have had a long history.  The latest variant is "ncurses" (new curses), which is has been available for years on unix-style systems, including Linux.  

Because this library is so well known, my first search for a TUI library involved looking through the hackage database for curses bindings for Haskell.  There are no fewer than 4 different libraries for accessing ncurses from Haskell.   The two that seemed to offer good coverage of the C library and that were relatively recently maintained were:
The first of these, hscurses, appears to be the most complete of these two.  It has a bindings for the C functions in ncurses and a few extra modules providing utilities, including a module defining a "widget" abstraction on top of the basic curses functionality.  

Experimenting with hscurses is pretty straightforward, though you can see how quickly application code gets complicated due to the relatively low-level nature of addressing a cursor around the screen.  Terminal resizing is supported, but if you want any persistent content, this must be stored and redrawn when ncurses is effectively restarted with a new terminal size.  One strange thing about the library is that it appears to miss a key binding to the function that sets the 'background' of a window (the name of a simple area of the screen configured in curses).  It's interesting to note that the widget module does not use windows at all, but rather draws directly on the top level screen 'window'.

The ncurses library makes a claim to providing a much more convenient programming interface.  This isn't a simple one-to-one mapping of the C interface to Haskell functions, and the few code samples to illustrate the difference look compelling enough.  Unfortunately, the library doesn't seem to work properly on the Mac (maybe elsewhere?) for its colour features, because the maximum number of colours reported for the terminal is "-1".  Perhaps this is not supposed to be a signed value, but in any case the library refuses to allow colour configuration because it expects this value to be a positive value greater than zero if colour configuration is allowed.   ncurses also has support for "panels", which allow 'overlapping' windows of the sort needed to implement menus, forms and dialogs.  That would be a great addition on top of the working basic functionality. 

In the final analysis then, both of these libraries have issues, albeit probably quite easily fixable.  Both are also quite low level and even some simple experimentation reveals how much housekeeping and legwork is required to achieve a reasonable effect.  

However, there's at least one more option.  On the Haskell IRC channel, the "vty-ui" library was suggested to me as a possibility.  This is a library that is designed to provide a much higher-level API for creating Text User Interfaces.  Written by Jonathan Daugherty at Galois, the library appears to be actively maintained and has excellent documentation - something of a rarity.

In chatting with Jonathan, it's apparent that the vty-ui library currently does not support overlapping widgets of the sort made possible with 'panels', but rather just a flat tiling of widgets like the basic ncurses functionality.  Nevertheless, vty-ui is the library that I'm exploring for use making TUIs.


GUI libraries in Haskell

The choice of Haskell GUI library looks like a minefield.  There are many offerings for writing GUIs in Haskell, but broadly speaking the options fall into two camps:
  • Fairly direct bindings to established GUI toolkits
  • More idiomatic 'functional' approaches for configuring GUIs and the events that flow between elements and application logic
The latter category was the one that piqued my initial curiosity.  After all, when you're in a programming environment with a strong flavour like Haskell, it seems reasonable to use the most natural methods to express things.   Of course, whether the most elegant functional stylings are necessary the most 'natural' begs the question "Natural for whom?".  Nevertheless, I investigated which high-level GUI libraries existed with a view to figuring out which are the most established and popular. With GUI programming being so ubiquitous, I was expecting a clear leader or two.

These high-level languages are typically based on the concept of "Functional Reactive Programming" (FRP).  In a nutshell, this works by 'wiring' up event streams between producers and consumers.  The libraries I looked at all used the very general compositional power of "arrows".  

Sadly however, I could not find a single high-level GUI library that was established and well maintained.  These libraries appear to have quite short shelf lives.  Many seem to begin as research exercises, manifesting ideas enunciated in academic papers.  They have a burst of attention and updates, but then get abandoned.  Probably, this abandonment is due to a combination of factors: novelty/learning-curve, limited functionality and general lack of uptake in the developer community.  

If there's no good choice for a high-level GUI library yet, then what about the lower-level Haskell wrappers for the GUI toolkits?  The two currently active such libraries are:
Out of these two, wxHaskell comes from a motivation to provide a full cross-platform GUI abstraction. Consequently, it is rumoured to work well on Windows.  Conversely, gtk is very mature and hugely popular, but it comes from the Unix/X11 world, so support for Linux will be very strong, followed by Mac OS X, with Windows likely to be a distant third.  

The last updates of these two packages were recent...ish, with wx having been updated May 2012 and gtk in Nov 2013.  While such dates aren't particularly significant, it might suggest that more people are interested in the gtk binding.  Certainly, the Haskell GUI apps that I have used (Leksah, threadscope) and several examples posted on YouTube are using gtk.

So, my limited survey of GUI toolkits seems to conclude that gtk2hs is currently the best option.  
I have consequently begun to play with gtk2hs on the Mac, along with the glade-3 GUI builder tool for creating loadable XML UI descriptions.  

One wrinkle with gtk on the Mac, is that the standard gtk 'back end' uses X11 as the underlying graphics stack.   While X11 apps are quite nicely supported under Mac OS X via the XQuartz app, nevertheless apps running under X11 still seem a little 'foreign' as they take longer to start up if X11 isn't already running and have other look and feel details that don't seem quite right.  There is however a Quartz backend for gtk that aims to solve most of these issues.  This appears to have to be linked with individual apps, so I'll have to figure this out some time.  In the meantime running under X11 works just fine. 





Tuesday, April 16, 2013

Amazing Mouse (Squeak the Last)

This is the last post in the Amazing Mouse series.

We're going to round out the application with some IO so that we can track the mouse through the maze.  We'll print the state of the world (maze plus mouse) for each move that the mouse makes and we'll pause for a key press between each move.

In the process, the following concepts will be introduced:
  • IO in Haskell 
  • Getting a package from Hackage using cabal
  • Using a library function from the installed package
We're going to print the maze on the console.  We can use the original character maze (CharMaze) for this, rather than converting the Material maze (Maze) back to characters.  However, we need to create a function called markLocation that will replace one character in the maze with the position of the mouse (representing the mouse as a different character... a dot).

The markLocation function needs to take a coordinate for the location of the mouse, and a CharMaze. It will then return a CharMaze (with the location of the mouse indicated).  The type is therefore:
markLocation :: (Int,Int) -> CharMaze -> CharMaze

In order to deconstruct and reconstruct the maze with the mouse location replaced with a dot, the markLocation function will need to do the following:
  • Separate the rows into those before the mouse location row, the mouse row, and those after the mouse location row
  • For the row containing the mouse, separate the row positions into those before the mouse, the character with the mouse, and the positions after the mouse
  • We can then build a new mouse row, with the character position of the mouse replaced with a dot
  • We can then rebuild the maze, with the rows before, the new mouse row, and the rows after
Here's a definition for this transformation:
markLocation (x,y) map =
    let
        (beforeRows, theRow : afterRows) = splitAt y map
        (beforeItems, _ : afterItems) = splitAt x theRow
        newRow = beforeItems ++ '.' : afterItems
    in
        beforeRows ++ newRow : afterRows

We are making use of the splitAt standard list function to divide a list into two components.  It so happens that the second list after the split always includes the item at the split position, so it's easy to split this individual item off the front of this second list using the list cons operator (:).  In the case of the  rows, we bind the name theRow to this single row at the mouse (split) position.  Similarly, when we deconstruct the row 'items' we bind names for beforeItems and afterItems, but this time there's no point assigning a name to the character at the mouse location as we're about to replace it with a dot.

To create a new row, we do everything in reverse, constructing the new row out of the beforeItems appended to the list made from the dot character cons'ed with the afterItems.

Finally, we similarly recompose the rows, with the beforeRows appended to the list of rows made up of the newRow cons'ed with the afterRows.

We're now ready to make the function that will plot a sequence of maze states, one for each mouse location in a given Path.  This involves doing IO for the first time in this project.

Haskell's IO is extremely clever, but you won't have seen anything quite like it in any other language.  Because function purity is sacrosanct in Haskell, we are not allowed to do anything in a function that directly causes or uses side-effects.  IO is a huge elephant in the room when it comes to being side-effect free, because side-effects are the whole point of IO!  The clever thing about Haskell is it does IO by not performing the IO directly in regular functions, but allowing you to create and compose together IO operation values that are then 'performed' in the right sequence at the right time.  The right time is when the main function in your program has to perform the top-level IO command in order to get anything done.  At this point, all the IO commands are 'performed', along with the regular functions that were glued into them to do normal things like adding up numbers.  

The biggest thing to remember about using Haskell's IO features is that if you're defining a function that returns an IO operation value then you're in this special world.  You'll be using some special ways to compose together IO operations to make bigger IO constructs.  It's all quite cute when you get used to it, but there are some more special functions to learn, and some special syntax called "do notation" that makes composition of IO sequences more convenient.  In fact, when you're using do notation, you're doing something very similar to using an imperative language embedded in a functional language.

With some scene-setting out the way, let's start by thinking about the type of the function (we'll call it plotPath) that we want to create:
plotPath :: CharMaze -> Path -> IO ()

The arguments here are straightforward.  plotPath will take an original CharMaze and a Path to plot. The original CharMaze will be modified with markLocation at each step in the given Path, then printed to the screen.  We'll then wait for a character to be entered at the keyboard with the getChar function.

The return type of plotPath is one of these IO operations.  In fact it's the IO operation that has no residual value, which is represented by the unit type that we mentioned previously when discussing tuples.  Output IO tends to leave no 'residue' (the values are 'gone' to the output device), whereas input is all about obtaining some value that is the residual of the IO.  The type of getChar for instance is:
IO Char 
... indicating that a character is the result of performing this IO operation when that finally happens.

Here's the definition for plotPath:
plotPath charMaze path = forM_ path printMazeAndWait
    where
        printMazeAndWait point = do
            forM_ (markLocation point charMaze) putStrLn
            getChar
           

The first line of the definition "forM_ path printMazeAndWait" works just like a 'foreach' in imperative languages, however it builds a sequence of IO operations, each operating on one element from the list of values provided.  In this case, we're saying "for each location in path, do the printMazeAndWait operation".  Again, it's important to remember that these functions are only composing together IO operations that will eventually be performed later by something underlying the main function in our program.

In the 'where' part of the definition we define this output IO function in turn.  Clearly, from the foregoing, this function takes a point (a location) as its argument.  We then use Haskell's "do notation" to glue together a sequence of IO operations...
  • First, for each row in the transformed maze (using markLocation) we print the row to the console (stdout) with a newline after each row.
  • Then we wait and obtain the next key press from the console (stdin)
The result of this function is the IO () value representing all these IO operations combined and in order.

We need one more utility function to be ready to finally put this through its paces.  This is a function that brings together generating a single path for a CharMaze and then showing it on the screen:

plotFirstPath charMaze = plotPath charMaze $ head $ 
                                             mousePathsFromStart (materialMaze charMaze) 1


Now, we can finally complete the main function that is the entry point of the program and the top-level IO operation that gets performed.

main = do
    putStrLn "Press space to move mouse one step"
    hSetBuffering stdin NoBuffering
    hSetEcho stdin False
    plotFirstPath charMaze0
    putStrLn "\\o/ The mouse lived happily ever after!"

Again, we use the "do" syntax to sequence some IO operations that represent the root of the program that will execute when you run the binary in the console.  There are a couple of special IO commands here for technical reasons:
  • "hSetBuffering stdin NoBuffering" just makes sure that the input IO system doesn't wait for a newline before making characters available to the program (otherwise getChar will not behave as expected to pause the program between maze drawings).
  • "hSetEcho stdin False" also turns off the echoing of typed characters to the keyboard.  We want getChar to do its thing 'silently'.
If you compile and run the program, you should see mazes scrolling up the console when you press keys, until the program completes. 

To go the final mile, we'll make a change to clear the console between maze drawing for a better effect.

To do this, we'll engage the services of one of the very many additional packages from the hackage repository.  This one is called "ansi-terminal" and it provides a "clearScreen" function that will clear any ANSI terminal screen.  This should certainly work on any Unix and Linux system.  YMMV on Windows!

To hackage repository has a browser allowing users to see packages by category and to search for packages.   All the available packages are obtainable using the standard package manager tool for Haskell called "cabal".   Cabal is installed automatically when you install the Haskell Platform, which is the standard way of obtaining Haskell these days.  Cabal takes care of downloading, building and archiving packages in standard locations.  As most modern Haskell IDEs use cabal packages for projects, building projects (e.g. in EclipseFP or Leksah) will automatically invoke cabal to build the package artifacts (applications or libraries).  

Both EclipseFP and Leksah have a way to declare external package dependencies for your project.  
In EclipseFP, double-clicking on the "<name>.cabal" node near the top of the hierarchy in the Project Explorer will open the cabal properties editor.  Clicking on the "Executables" tab will allow package dependencies to be added to executables included in the project cabal package.

In Leksah, the cabal settings are available from the Package -> Edit menu and the "Dependencies" tab provides a similar editor.

Whichever IDE you are using, you will need to add "ansi-terminal" as a package dependency.  Then, this package will need to be fetched and installed.  Both EclipseFP and Leksah have means to install dependencies from within the IDE.  However, this can also be done from the command line with the cabal tool:

> cabal install ansi-terminal

When you execute this command in the shell, you should see messages indicating that the package is being fetched, built and installed successfully.  Cabal has the ability to transitively fetch and install dependencies, so several packages might be obtained and built whenever you request a specific package for inclusion in a project.

Having installed ansi-terminal and added it to our project dependencies there are only a couple of things left to do to use it...
  1. Include an import statement for the modules you need from the package.  In this case we need to add: import System.Console.ANSI
  2. Add the line "clearScreen" beneath "getChar" in the printMazeAndWait local function of plotPath.  
When the application is rebuilt and run, you should see the effect of the clearScreen between key presses and maze drawing (assuming you are running the application in a shell in a ANSI terminal window).  

So that just about wraps it up for the Amazing Mouse exercise.

Haskell can initially be a steep learning curve, especially when cross-training from imperative/procedural and OO languages.  However, as is always the case, immersion and experimentation are the fastest paths to enlightenment.  

I've tried to strike a balance in this example of explaining enough to avoid big mysteries, but invariably there will be gaps if you are completely new to the language.  That being the case, I would highly recommend the book "Learn you a Haskell for Great Good".  Once past the first half-dozen chapters, then this example should make a lot more sense!

There are plenty of ways that this example, as presented, could be improved for efficiency and style, let alone adding a few more bells and whistles.  I may subsequently post a few suggestions in case anyone lacks imagination (!) but wants to tinker some more.






Monday, April 15, 2013

Amazing Mouse (Squeak the Second)

Continuing our maze solving Haskell programming example, we now get to the interesting stuff involving navigation about the maze.

Maze solving is a classical search problem, involving the following basic concerns:
  • Generating one or more solution 'paths'.  Where...
  • Each path is a list of visited locations from the Start to the Exit.  Where...
  • At each step, we explore the possible next steps in some order of preference and we never consider moves that would cycle back to a previously visited location. Where...
  • Next steps can be generated from the current location along the path by sampling all the locations around the current location and determining which adjacent locations are navigable (not a Wall!)
So the algorithm is basically a multistep 'generate and test'.

The most basic ability to provide our virtual mouse, is the ability for it to determine which adjacent locations can can be visited.  For a given x y location, we will need to consider the eight possible adjacent locations (we'll allow our mouse to move vertically, horizontally and diagonally around the grid to any non-Wall location).

What are the rules for generating 'legal' pairs of (x,y) move-candidate locations around a current location?
  • The location can only be -1, 0 or 1 squares removed in either x and y coordinates.
  • ... but the location may not be 0 squares removed in both x and y, as this is the current location.
  • The location must be legal in the maze (no smaller than 0 x or y, and smaller than width in x, smaller than height in y).
  • The location must not be a Wall
Given that we're generating another list (of candidate locations around the mouse), this is another job for a list comprehension.  Here's the code:

possibleMoves maze x y = [(x',y') | x' <- [x, x - 1, x + 1], y' <- [y, y - 1, y + 1],
                        not (x' == x && y' == y),
                        x' >= 0, y' >= 0, x' < mazeXMax, y' < mazeYMax,
                        materialAt maze x' y' /= Wall
                        ]
                where
                    (mazeXMax, mazeYMax) = mazeSize maze

Recall that a list comprehension has list constructor syntax (square brackets), with the first term in the brackets (up to a vertical bar) being the constructor for individual elements of the list.  So, we're going to be building a list of (x',y') pairs.  The apostrophes perhaps look unusual, but they are just characters that Haskell allows in identifiers that are borrowed from mathematics.  You can read them as "derived" i.e. we're constructing a pair "derived x" and "derived y".  Mathematicians call the apostrophe "prime", by the way, e.g. x' is pronounced "x-prime".

The rest of the clauses in the list comprehension match the rules we outlined above, that generate and test possible new locations, given the original location x y that are provided as arguments.  

To begin with, we generate possible derived x and y candidates by taking the current coordinate, the immediately preceding coordinate (one space to the left/up) and the immediately succeeding coordinate (one space to the right/down).  

Then, we ensure that this candidate location is not the current location (where x' == x and y' == y).  

Next, we check that this location lies properly within the bounds of the maze.  We use names "mazeXMax" and "mazeYMax" that are bound in a where clause at the end of the function definition, again using our mazeSize function to obtain this.  This is another potential inefficiency, as we'll be recalculating the maze size every time possibleMoves gets called, but this doesn't cost that much ;-)

Finally, we test to ensure that the candidate location is not a Wall using materialAt.  In the current implementation, only the Wall Material is not traversable in the maze.

Now, our mouse can 'see' around him and discern possible directions to travel in the maze.  However, he still has no idea which direction might be best.  We could provide no distinction at all between the possible moves the mouse could make, in which case the mouse would have to make an essentially 'random walk' through the maze (albeit being able to refrain from doubling back on himself).  Alternatively, we could provide the mouse with some ability to sense a better direction to travel - perhaps he can smell the pile of cheese lying just beyond the maze exit, or maybe he has some general sense of the direction of the exit. 

Let's give the mouse a general sense of direction to the Exit, rather than model any particular physical manifestation that might indicate the direction of the exit.  We'll allow our virtual mouse to know an approximate distance to the Exit from any location (thus, the possible locations of a move).  This will help discriminate between possible moves, but it will not help the mouse avoid the obstruction of maze walls, as distance is independent of such obstacles.  

OK, so let's create a distance function.  This will return some distance metric for any two locations (given by two pairs of x,y coords).  A true distance would involve the full Pythagorean equation, e.g.:
distance = sqrt(deltaX^2 + deltaY^2)
However, we don't really care about the exact distance.  We only need a distance score with which we can order a set of locations.  Consequently, it is sufficient to use:
distanceSqr = deltaX^2 + deltaY^2
or frankly, even the sum of absolute distances in x and y would do.

The actual code should be pretty straightforward by now:
distanceSqr (x,y) (x',y') = deltaX * deltaX + deltaY * deltaY
        where
            deltaX = x - x'
            deltaY = y - y'

Note that we're again unpacking two data structures (the coordinate pairs) in the argument list (LHS) of the function definition.  

Now that we have our distance function, we can specialise possibleMoves with a new function orderedMoves that will sort the locations from possibleMoves using their distance from the Exit.

orderedMoves maze x y = sortWith (\location -> distanceSqr location $ exitLocation maze) $
                                            possibleMoves maze x y

The sortWith function uses the result of a provided function as the property on which to sort any element (in this case a location).  Sorting will be ascending, which is what we want.  The nearest locations will end up toward the beginning of the resulting list, and the more distant locations at the end.

Armed with some orderedMoves to try on each step along the path toward the Exit, we're now ready to generate paths through the maze.  We'll create a function that returns an arbitrary number of possible paths that the mouse could take given the navigation rules we're coding.  Again, this will be a 'generator' kind of function, and later on we can write functions that, for instance, just take the first path found, or take some number of generated paths and return the shortest.

Let's write the type declaration for a function mousePaths:
mousePaths :: Maze -> Int -> Int -> [[(Int, Int)]]
This says that mousePaths will take a maze, two integers (actually an x and y starting location) and will return a list of lists of pairs of integers.  The inner list here is of course a path (a list of locations defined as (x,y) coordinates).  

Actually, that last type is a bit ugly, but we can clean it up by saying that the inner part has a name "Path":
type Path = [(Int, Int)]
in which case the type of mousePaths can be rendered:
mousePaths :: Maze -> Int -> Int -> [Path]
... which is a lot more readable.

Let's now think about how to generate paths.

Clearly, a path can be constructed by recursively choosing a new location from the end of the current path.  If the initial path is just the starting location, then we'll 'grow' a path from this point, using orderedMoves to select a new location from the last location.  

One important rule that we'll build into the path generation is that we won't let a path double back on itself.  This is easily achieved by disallowing any proposed new location that already exists in the path list we've already build (the locations previously visited). 

We know when we have a new complete path to return when the next location is in fact the exit location.  

Here's a definition for mousePaths, that captures the above strategy:
mousePaths maze x y =
    let
        exit = exitLocation maze
        mousePaths' path = do
            let (thisX, thisY) = head path
            next@(nextX, nextY) <- orderedMoves maze thisX thisY
            guard $ not $ elem next path
            let newPath = next : path
            if next == exit then return newPath else mousePaths' newPath
   in
        map reverse $ mousePaths' [(x,y)]

A lot of the discussed rules should be recognisable right away, but there are a few things to pull out for discussion.

The mousePaths function is provided with the maze and an initial x and y value.  We need to define a recursive 'helper' function that deals exclusively in the paths that are being built (again, a path being a list of (x,y) location coordinates).  This local helper function (mousePaths') is defined in a let block along with a definition to obtain the exit location from the given maze. 

The outer function, simply kicks off the search for mouse paths by calling mousePaths' with an initial path containing only the current location, constructed from the starting x and y coords provided as arguments.  Because paths are built up as lists (with the last location visited being the head of the list) we will need to reverse any paths that are returned by the mousePaths function; hence the "map reverse" applied to the list of paths returned by mousePaths'.

Clearly, the real meat of this function lies with the helper function mousePaths'.  While the type of this function is not provided in the source, it is quite interesting:
mousePaths' :: Path -> [Path] 
You can copy this type declaration into the source above the definition of mousePaths' if you want to verify this (or indeed to better annotate the source!).

This means that for any Path that this function is given, it will return a bunch of potential Paths.  In other words, mousePaths' represents the strategy of generating alternative new Paths, given some rules, from some initial Path.  In this case, we'll be extending the initial Path with new locations from the orderedMoves list on each iteration.  

As a side note, this is an example of a branching computation.  From some initial 'seed' path, containing only the starting location, we are continually splitting into new Paths one per legal move, each of which in turn split again (on recursion).  Thus, we 'concurrently' explore all the possible paths that are allowed by the branching rules.  

The body of the mousePaths' helper function defines the branching rules for exploring multiple Paths.  First, we simply get the last location of the current path we're processing.  This is the head of the path list.  The coordinates thisX and thisY are extracted from the location coordinate pair.  

Now we need to determine the potential next locations to which we could move.  We use orderedMoves to do this, so that the 'best' locations are tried first.  Note that the left arrow in this line works exactly the same as the left arrow in a list comprehension (in fact we're really doing another list comprehension, just in a different format!).  Each item returned by orderedMoves will therefore be bound to symbols on the left hand side of the arrow, which in this case is a pattern match to extract the location details nextX, nextY and well as preserving the original location pair returned by orderedMoves as next.   The commercial-at sign (@) used in pattern matching simply allows us to bind a name for the whole value, at the same time that we use pattern matching to extract details from the value. 

Just like the earlier list comprehensions, once we have a candidate value for returning, we can test to see if it conforms to some rules.  In this case, the only extra criterion is that the new location must not be any of the locations previously visited so far in this path.   To do that, we simply assert that the next location is not an element (elem) of the current path.  The 'elem' function is from the standard list library.  Whereas we were able to express predicates like this directly within a list comprehension, outside of this we must use the guard function to apply a predicate and decide whether to reject the current proposed next location (and therefore path under construction).  The guard function is from the standard Control.Monad library.

If our proposed next location survives the guard, then we consider it fit for extending the current path.  Commensurately, we build a newPath value by prepending the existing path with the next location.   Again, we're building up the path at the head of the list, because lists are only cheaply modifiable in their initial value.  

Having determined the new path, all that remains is to decide whether we have 'arrived' at the Exit location.  If we have then this defines a complete path, which is returned as a 'result' Path from mousePaths'.  Otherwise, this partially constructed path to the Exit still needs further 'moves' to extend it to the Exit.  Of course, the function that extends any single Path is mousePaths' itself, so we just make a recursive call, but with newPath.  

Hopefully, you were able to follow all the logic here, but it may take a few reading passes.  

There is a little 'magic' operating beneath the hood here, but it's exactly the same as a list comprehension.  This magic is simply that lists in Haskell belong to a Type Class that implements a branching computation strategy, where a single initial value (e.g. Path) can expand into a list of values (e.g. Paths).  The 'guard' function requires this membership, as it is used to prune away rejected paths (which are represented as empty lists).  We only ever get to see lists in the result that have not been 'rejected' in this way.  In any case, this behaviour (and of course list comprehensions) are absolutely standard features of Haskell and its core libraries.  

The final addition in this episode will be to simply wrap the mousePaths function with function that provides the start location and only returns a set number of Path solutions.

mousePathsFromStart :: Maze -> Int -> [Path]
mousePathsFromStart maze n = take n $ mousePaths maze startX startY
    where
        (startX, startY) = startLocation maze

There shouldn't be anything surprising in this definition, given the foregoing.  

So, that's a wrap. 

In the next instalment, we'll add some console IO to plot mazes and the movement of the mouse step-by-step.

Next> 

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:
[Char]
(... 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
    where
        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 "let...in" 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
    where
        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.

Next> 

Amazing Mouse (Introduction)

The first problem we'll work through is a little puzzle solver called "Amazing Mouse".

The idea is that we will define a two dimensional maze, with a starting point for a virtual mouse, a target exit point (or perhaps the location of some cheese) and the traditional maze walls around which the mouse has to navigate to locate its target.

The maze will be specified as a grid of 'materials', where the legal materials are:

  • Empty - a square through which the mouse can travel
  • Wall - a solid wall that prevents passage of the mouse
  • Start - a special 'empty' square that represents the starting point of the mouse
  • Exit - a special 'empty' square that represents the target point of the mouse
Over the course of the worked example, we'll build up to a solution that draws the maze with the location of the mouse for every move that the mouse makes.  

This example was chosen as a simple toy problem that nevertheless presents ample opportunity to introduce quite a range of Haskell features.  If fact, in due course we'll see:
  • Importing library functions
  • Defining new Abstract Data Types 
  • Use of some predefined Type Classes
  • Defining functions (of course!) with local let bindings of functions and values
  • Pattern matching to decompose structures to obtain embedded values
  • Giving compound types new names: type aliasing
  • Anonymous functions: lambdas
  • Application of functions to fewer arguments than defined: partial application
  • Lots of list manipulation (demonstrating lists as a representation of sequences)  
  • Convenient list building with list comprehension syntax
  • The use of cabal to obtain and use a non-standard library
  • ... and finally a little bit of IO to print mazes and wait for key presses
In order to follow along, you'll need to have the Haskell Platform installed on your computer.  
The Haskell Platform is the recommended Haskell SDK, it consists of the Glasgow Haskell Compiler (GHC) compiler tools, a package manager (Cabal) and a range of 'canonical' preinstalled libraries.  

You can of course use any code editor you have lying around (or prefer).  However, you might like to see if there's a Haskell source mode at least for your editor as this will provide a few extra helpful features (like syntax highlighting).  If you don't have any particular preferences, then I would recommend the following IDEs:
  • Leksah is an IDE designed for Haskell and written in Haskell.  It's still quite young, so has limited features and a few minor bugs.  It runs on Windows, Linux and Mac OS X.  I recommend checking the forums for the latest updates.
  • EclipseFP is a plug-in for the ubiquitous Eclipse IDE.  Eclipse is a full-featured IDE written in Java.  Once you have Eclipse installed, then adding the EclipseFP plugin is relatively straightforward (though it can take a while for all the dependencies to compile and install).  EclipseFP probably represents the leading edge of Haskell support in any IDE at the time of writing.
Once you have the Haskell development tools all installed, the first order of the day will be to create a new Haskell project.  These days, Haskell projects are usually cabal projects.  Cabal is the aforementioned package manager for Haskell.  A Cabal Package is a little versioned archive of Haskell sources and resources that can depend on other cabal packages that are automatically obtained, built and linked together to make an application or library.  If you create a new Haskell project in EclipseFP, then you will be implicitly creating a new Cabal package in the project.  In Leksah, you create a new workspace and then explicitly create a new Cabal package within this.

Having created a new Haskell project, you will be presented with an initial Haskell source file, probably called something like "Main.hs".  Haskell sources typically have a .hs extension and they typically describe the contents of a single Haskell module.  A module is simple namespace package mechanism.  It fulfills the same role as a Java package or a C++ namespace.  Modules can import symbols exported by other modules (e.g. other local source files or shared libraries).  

The template Main.hs file that IDEs create in a new project probably has the following visible features:
  • Block and line comments.
    Haskell's block comments are delineated with {- and -} and its line comments are introduced with -- .  There are some special forms within comments that various tools look at.  GHC compiler pragmas are are delimited with {-# and #-}, so look like special block comments.  Haskell's inline documentation tool Haddock uses a vertical bar | to introduce comments that are intended to be extracted into documentation, e.g.:
    -- | This is a documentation comment 
  • The module declaration and export list.
    The first actual syntax in a Haskell source file is the module declaration and optionally the list of explicit symbols exported from the module.  In a project template, this will probably look like:
    module Main (
       main
    ) where
    The critical part of this is the "module Main where" syntax that declares the name of the module and the start of its definitions.  If the parentheses between the module name and the 'where' keyword are included then this can contain list list of exported symbols.  For a top-level module in an application project, the "main" function must be exported as this is the entry point of the program (just like C/C++/Java/C#/... etc.).
  • The first section inside a module is usually a list of import statements.
    There are a few special variations, but the basic forms are:
    import System.IO
    ... if you want to import all the exported symbols from the module "System.IO", and...
    import System.IO (hWaitForInput, getChar)
    ... if you had wanted to import just the two symbols "hWaitForInput" and "getChar"
  • After the imports come the main body of definitions in the module.
    There are very few things you can define in Haskell and most of the definitions in a module will be functions.  A basic function definition could look something like:
    nameOfFunction arg1 arg2 = doSomethingWith arg1 (andAlsoWith arg2)
    Notice that the list of formal arguments are just separated with spaces.  Everything after an '=' is the definition of the function and involves calling other functions using the arguments of this function.  Parentheses are used to control the scope of function application, so here arg2 is applied to the 'andAlsoWith' function, whose result is then applied to the doSomethingWith function in its second argument (after arg1).  
  • As this is a top-level module of an application, the entry-point function called main will be defined.  
The project template may provide a bunch of imports and functions definitions that we don't need.  So, we can begin my deleting all the module content except for this:
module Main (
    main
) where

main =
    putStrLn "Hello World"

This should compile and run using whatever IDE you have chosen.

In subsequent posts, I'll use this bold blue text whenever indicating some final code for inclusion in the source file (as opposed to code that is merely the subject of some discussion).

In the next post we'll start to build up definitions for the Amazing Mouse solution.




Haskell... is great

Haskell is a great computer language.

It's great to use and it's great to learn even if you will be spending time mostly with other languages.  This is because it represents, in a very pure form, many of the fundamentals of programming - that is how logic, calculation and action sequences can be expressed.

Many modern computer languages are packed with different programming structures and idioms that are intended to be pragmatic; tools for different kinds of problem the programmer will encounter.  Haskell is refreshingly simple in both concept and syntax.  That's not to say it's trivial to learn however, mostly because we pretty much all get our education in languages derived from Fortran and Algol.  To use Haskell you have to rebuild your mental wiring about programming abstractions in the platform Haskell provides, and of course your repertoire of idioms and library functions that you'll use to get things done.

Aside from just 'being different' and intellectually interesting though, there are some deeper things that make Haskell a fitter computer language - especially as we enter a new age of multi-core and distributed computing.  The very premise of how Haskell works is genuinely better:

  • There is no 'naked' shared mutable state.  Shared mutable state is like 'original sin' ;-).  It complicates and corrupts normal life and has pernicious effects on larger bodies of code.  In the absence of concurrency, its effects are not debilitating - you just have to get the logical sequence of changes right.  With concurrency, all bets are off!      
  • There are no pointers and no NULL.  Whole classes of bug are effectively removed as possibilities in one fell swoop.  
  • Functions are pure and subject to more automatic optimization.  Functions are a mathematical concept.  True (pure) mathematical functions are subject to a century of deep mathematical understanding in how they can be optimised via simplification. 
  • Lazy evaluation allows for clean, naturally readable algebraic definitions.  Lazy functional languages grow by combining the expressions.  This acts like a powerful and nearly invisible glue.
  • Functional composition is the central idea of Haskell.  Composition is the only way to successfully build very large structures from smaller ones.  That's because it doesn't pollute the derived structures with constraints and special behaviour arising from the design artifacts and other properties of the method used to bind together the semantics (e.g. the glue doesn't have any other effect than joining expressions).
  • It has a very expressive static type system that supports many kinds of polymorphism and has type inference.  Haskell figures out the type of code you write.  If you want, you can write code without writing a single type annotation.  You'll get the most general meaning of your code inferred so it will be useable in as many places as possible.  However, if you actually make a typing mistake then the compiler will tell you right away and you don't have to wait until that code path is executed at runtime to find out (maybe months later!).  
As alluded to above, where this gets really exciting is how this can help with the biggest challenge of computing we have today: parallelism.  Haskell fundamentally has all the features and no critical impediments that allow a program to be arbitrarily broken up and distributed across multiple compute nodes (whether CPUs or machines on a network).  There is still a lot of work to be done to make this automatic, based on an analysis of cost of moving code and data, but even today more can be done on a single multi-core machine and the nature of the language makes manual structuring of code for parallel execution so much easier.

More and more computer languages are adopting functional and lazy evaluation features.  Lambda functions are being added that allow functions to be passed as values like data and generators are being added so that sequences of values can be computed on demand.  Languages and libraries have adopted Haskell-style list comprehensions, and even monads (a higher-level functional programming idiom).  Yet, even as these features are transplanted to other languages, they only add to the bewildering collection of programming features in those languages and often their addition forces certain compromises on their use.  At the very least, communities of programmers will have to select which language features to use and when.  The choice of programming style has a huge effect on the degrees of freedom that code preserves for future reuse.  Conversely, Haskell remains uniform - everything is a function, the only arbiter of reuse and recombination is the type system, according to the values that the program is manipulating.  Because Haskell is focused on basic values rather than abstract structures of state and state manipulators, it is sometimes called "value-oriented programming".

Whatever piques your interest about Haskell, I expect to post a series of blog entries here on learning Haskell... mostly as a side-effect of introducing the language to my son.  It will be (hopefully!) focused on Haskell as a practical tool, compared of some discourses that discuss more technical/mathematical underpinnings of Haskell's features.