Sunday, April 14, 2013

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.





No comments:

Post a Comment