Thursday, November 14, 2013

Ramblings on Haskell's 'cognitive overhead'

Does Haskell have 'excessive' cognitive overhead?

The question about whether Haskell (or a very similar language) might one day become a popular language for solving the increasingly tough programming problems ahead of us (concurrency, distributed computing etc.) seems to come up quite often.

It's an interesting question.  

One of the great things about Haskell is that it does seem to have answers to big problems and those answers can be traced directly back in many cases to the defining fundamentals of the language (universal purity, composability and to some extent laziness).  Pure functional programming tackles many of the ills that beguile software today.  That ideas from the functional programming world are highly valuable is less and less controversial, as features like lambda functions/closures and even monads are being imported into other languages and their libraries with gusto.  

However, those features alone aren't the sum total of Haskell.   Indeed, Haskell is characterized as much by its powerful type system as it is by its exclusive use of functions for expressing computation.  Haskell's type system is also differentiated from most other languages in that, while static, it is also inferred - so for the most part the programmer never has to write type annotations… as much as this is considered good practice.  This property is very hard for imperative languages to achieve in general (although languages like C# have introduced limited forms of it).  

I have watched many developers, who have spent most of their careers being trained and practiced in imperative programming, attempt to take to Haskell.  Admittedly most of these developers have not spent much time thinking about and using functions as first class objects, even as these have been added to imperative languages.  That's because most developers I know have spent years with Java, which unfortunately has been a laggard in terms of first class functions.  Nevertheless, most programmers do believe they understand functions when first asked to compare their experience with what they think they'll find in Haskell.  What they may be unaccustomed to doing however, is thinking exclusively in terms of functional composition.  

Invariably, there's a lot to learn when approaching a new language, and even more when meeting a new programming paradigm for the first time.   
Haskell presents a number of potentially avoidable initial challenges to those seeking to learn how to use it effectively, for example:
  • Tutorials are getting much better, but traditionally have been couched in mathematical terms of reference.  Even today, a lot of conversations on Haskell language features and programming issues are discussed in terms that the average software developer will find completely foreign.  Unfortunately, it seems that the established Haskell community enjoys a certain amount of this mystique and even some outright ‘occultism' ;-)  
  • Similarly, Haskell's library documentation, especially beyond the standard libraries, is somewhat sparsely documented.  Neither does it help that Haddock generates type signatures for functions, but does not include argument names.  Argument names are also often incredibly terse in many Haskell libraries and programs, but where they do convey useful information this does not appear in the resulting Haddock docs.  This can make browsing and discovery of library functions more difficult that it should be.  There are plenty of examples of functions with arguments like drawRectangle :: Widget -> Bool -> Int -> Int -> Int -> Int , where the meaning of most of the arguments is completely opaque.  
  • Developers used to IDE support have been somewhat challenged with the support for Haskell, although again this is improving nicely with EclipseFP and Leksah.  Even so, it is remarkably hard to search for functions when you know some arguments or some type that you want.  Hoogle is one tool that purports to do this, but I still find this very awkward and I've been playing Haskell for years.

Notwithstanding these peripheral issues however, for imperative programmers new to the Haskell language the real unavoidable conceptual displacement surely comes with:
  • Learning how to think in terms of composing functions
  • Learning how Haskell's type system works
  • Getting comfortable with common language features and patterns like type classes and monads
  • Learning a basic 'vocabulary' of functions in standard libraries

The first two of these seem to present the largest overhead for newcomers.  The plain fact is that most people just have not created the mental apparatus to think naturally about function composition and polymorphism with the degrees of expressibility that Haskell's type language offers (although thankfully "generics" have been a feature of OO languages like Java and C# for years now).  

New tutorials like the excellent Learn you a Haskell finally provide an accessible and well-paced route through the material that seems to work for most developers converting to Haskell from the imperative world.  This has really helped with some of the 'unavoidable' learning curve. 

Once developers have genuinely grasped the fundamentals of Haskell, they are typically aware of the following dynamics:
  • It can take more front-loaded reasoning to get to an initial shape of a solution
  • The type system is an ever-present reality.  
  • Once the program compiles, it usually works solidly
  • However, it may not work efficiently or perform as desired (and then exploring and debugging a running program is quite a different experience)
  • It may also begin to dawn on them just how flexible and powerful functions are as a raw material - due to every function having its own 'interface' and being directly composable with other functions.  

Some developers when initially confronted with the ideas of Haskell, or perhaps as they are learning the ropes, start to emote that the type system is an impediment.  This seems to be a reaction that is far more pervasive when newbies connect with Haskell than it is when they pick up something like Java or C#.  Adding to this is perhaps the increasing exposure that programmers get to scripting and dynamic languages (such as Python, Clojure or Ruby) that can condition them toward code-test cycles that do not involve any form of compile time type checking. 

This gets us squarely into the discussion about static vs dynamic languages.  While this is a dichotomy that lies outside the scope of Haskell's advantages compared to imperative languages in general, it is nonetheless an important overall factor in how Haskell is perceived these days within the community of people likely to express an interest.  So, it's worth a bit of discussion on the topic.

People who support statically typed languages argue along these lines:
  1. Correctness in software is clearly critical
  2. Statically typing code is a way to get early validation and warning about a fairly broad category of problems that can exist in code (though runtime testing is essential for validating algorithms and workflows)
  3. Computers are extremely good about managing large quantities of detail.  Humans are good at planning and design, but can only focus on a handful of things at once.  Ergo, it's advantageous to have the computer play a role as a correctness tool for details as software is being developed.  Types provide low-level coverage of general details, where runtime testing provides higher-level validation of behaviour (but only for things you remember to test). 

People who support dynamic languages argue along these lines:
  1. All that really matters is whether some code eventually behaves correctly compared to its requirements.  
  2. Therefore runtime testing is the only thing you need if you are disciplined enough to write appropriate tests as you write your program logic.
  3. The cost of managing the annotations required to feed a static type checker to verify your code is outweighed by the benefits of just coding and writing tests.

Given that the use of dynamic languages in large, complex, software projects is a relatively new wave, I think the jury is still out of how the economics play out over the full lifetime of a large software system.  I'm certainly very curious to hear and read of experiences with this software practice.  However, I am already well aware of a number of projects that have gone very much off the rails, specifically with the use of Ruby at large scales.  

One aspect of all this that seems common sense (to me!) is that software development is an extremely human activity.  As we scale up the number of people actively engaged on a software project, we naturally have to be concerned with:
  • Division of labour and responsibility
  • Practical and effective coordination
  • Good communication (intent, architecture, design and implementation choices/constraints)

Personally, I think this social aspect of development is under-discussed as a determinant in the appropriate choice of programming language.  

The concept of contracts is essential in any activity that involves multiple actors.  These may be formal or informal, technical, legal or social contracts.  
What's pertinent to this discussion is that groups of developers have to establish and maintain many agreements between parties if they are to be efficient (which includes reaching an acceptable implementation quickly and finding problems with quality as early as possible).  Many agreements are not formalized and checkable by computer, e.g. who works on what, who accepts work as complete, what libraries should be used.   However, where we choose to divide up the design of software (for problem decomposition or assignment of responsibility) we create the need to agree contracts.  Software contracts are typically called interfaces of course and these are something that can be formally expressed and checked by a computer.  Preferably, the checking should be both types and behaviour - but type checking alone is nonetheless highly valuable as a computed proof of some very important properties of an interface.

It seems to me, while pondering some of the disasters I'm aware of, that dynamic vs static issue should be rather more nuanced than it is often played out.  I suppose people find it easier to cleave to black and white positions, as much as many people also like to flock together when taking a line on technology (usually motivated by their own prior investment in skills).  In truth, the value of formalizing contracts and interfaces does change with scale.  I might ask the neighbour's son to rake some leaves on the lawn in exchange for a small fee, but if I'm engaging a company to paint my house then invariably we'll want to ascertain more precisely what gets done and for what price.  Similarly, a dynamic language (we used to call many such things scripting languages) can be a very lightweight way to express solutions to small problems.  By small I probably mean a few tens of pages or code, or perhaps a few 'modules', but in fact that is proportional to the collective 'detail capacity' of the actors involved.  This is a very interesting part of the problem.  

It's far more likely that a single author can construct and memorize details of code they've personally created.  Of course, the passage of time is well known to disrupt this, but still.  
I have seen high-quality teams of a half-dozen people informally maintain the quality social contracts, discipline and communication necessary to keep everyone well-coordinated in software projects.  This works well when there is a strong sense of leadership or shared values in the team that can make it a 'high context' environment in which people mostly just know what the right things to do.  
However, there's a point where, whether by pure scale or by heterogeneity (dislocation, politics, disagreement, competition), a team will simply not be able to function with the requisite cohesion to allow informality, culture and values to constrain possibilities enough for efficient progress of the group as a whole.  At some point more formal contracts become highly valuable and arguably therefore so does well-typed interfaces.

Given the foregoing discussion, I would characterise Haskell as being an appropriate language for high-complexity, large-scale projects.  

However, as discussed, it is also differentiated from most statically typed languages by virtue of having almost universal type inferencing.  This means that theoretically you don't have to write a single type declaration in your program, but Haskell will still have the power to check and reject bad programs.  Of course, that's different to having no type checker at all, but it goes some way to addressing a complaint that you often hear from proponents of dynamic languages: that they'd like to write code without having to spend time writing out and managing a bunch of types as they add and modify things.  In that sense Haskell makes a great prototyping language, but I would add another aspect too.  In many languages, there's a lot of boiler-plate code to capture essential structural elements that are required by the language design.  In languages like Java and C# for instance, you will be typing quite a lot of just to express the minimum wrapping of code in a class or two, or code to express accessor methods on properties.  That's different in something like Python or Ruby where there is implied encapsulation for 'naked' code, and this is also true to a great extent in Haskell.  In Haskell, every function has its own interface, so you certainly get to experiment with combining them much more freely before you ever need to start thinking about the distillation of design structure (e.g. custom data types, type classes, etc.).  

Ultimately, you will be dealing with types in Haskell however, no matter what might happen at the small scales of prototyping and trivially small projects and experiments.  So you will certainly be thinking about types you're consuming and probably types you're producing.  If you consider this an overhead, then you certainly have to place it into the context of the cost:benefits of contracts in general.  As projects get larger, the nature of where the costs and benefits actually are changes.  With more actors and separation (of code and people) there are more interstitial elements.  Are these challenges going to be managed purely socially, or are they going to be at least partly formalized and checkable by a computer?

Given that the type system is one of the more unique things about Haskell, at least as differentiated from most other languages people will be using in commercial software development, I suspect that this is where most of the "cognitive overhead" lies.  Gaining intuition about functional composition is a close second, followed by learning common libraries (which isn't a conceptual issue and is a common problem when converting to any new language).

In very practical terms, the most stumbling blocks I've seen with newbies are:
  • Understanding, in terms of type expressions, how functions work and what application does to a type. 
    That includes seeing a function type as a superposition of possible results (other functions).  Most imperative developers don't naturally understand application and partial application.  They tend to think of a function as having to consume all its formal arguments and producing a simple value. 
  • Interpreting type expressions and trusting them
    You can trust Haskell's type expressions in a much deeper way than you would an OO interface or method signature.  Imperative programmers tend to take a long while before they start trusting that type expressions are really awesome and that's the path to seeing Haskell's type system as your friend.
  • Understanding 'dispatch' on types, including the return type. 
    Functions like 'read' and 'return' can be completely mysterious to most OO programmers
  • Unnecessary confusion about monads.
    Too much fuss is made about monads.  They are called out as some strange new thing, whereas they are just a pattern in types (a wrapper around some value) with a way to produce new wrapped values from other ones. 
  • The relationship between 1st order and higher-order patterns is something that's probably net new to an imperative programmer and Haskell doesn't help with its current naming schemes.  I've always thought that "fmap" should just be called "map".  If you were going to qualify anything, the List.map should be "lmap".  History is what it is I suppose.   This also touches on the mathematical nomenclature issue.  To most people, "Functor" is an awfully scary name that suggest a hard-to-grasp new concept.  When people actually have it explained (or learn to read type expressions as they should) it's just such a no-brainer!

So far, we haven't considered features of Haskell that set it apart as having real benefits compared to most alternatives.
Amongst these are its fitness for concurrency and the value that laziness has in separating producers and consumers.

Concurrency (and to a lesser extent even wider-area distributed evaluation) is such a big and growing problem that every significant language and application framework vendor is scrabbling to find answers to offer to their developer communities.  Apple has Grand Central Dispatch, a framework for scheduling closures on serial queues and one system managed parallel queue.  Microsoft has its async library and C# language extensions for continuation passing and futures/promises.  

Haskell gets so many of the fundamentals right here, in a way that is very hard to retrofit to other languages.  It is difficult to see how it won’t continue to be held in ever higher regard as its fitter DNA continues to make it differentiated in solving the hardest problems.   Moreover, it achieves its benefits quietly and cleanly through not having sold its soul to the devil, even when it was by no means certain how some of the ‘simpler’ issues such as side-effects could ever be accommodated satisfactorily.  Meanwhile the popular imperative languages like Java, C#, C++ and Python are adopting features so rapidly that they are becoming a multi-paradigm mess.  It will be interesting to watch them continue to evolve, but also to see how the folklore develops in terms of how to wield their many features appropriately.   The naturalness of expressing various forms of concurrency in Haskell is of course a different thing to automatic concurrency (still no more than a pipe-dream), yet with Haskell you can freely integrate concurrency of various types with libraries without distorting any of the general idioms of the language or forcing heavy-weight design patterns.  Still, concurrency is unlikely to be an issue that a newbie would find essential to learn anyway, so while Haskell has many advantages here, this is also no an ‘overhead’ thing for learning the language.

In Haskell, lazy evaluation allows generators to be described at any time.  If you have a function that produces a thing, it's trivial to create a generator for a stream of those things.  This generator will be as easily consumable as any data structure, e.g. a list of things.  You don't have to create a specific interface e.g. "getNextThing" or worry about the states of enumerators and iterators.  This is a very powerful feature in a language that is essentially about the transformation of values and it is also representationally powerful in that it allows a fully algebraic style in the code.  The benefits are laziness then are that it defers details of usage and has the power to conserves generality and reuse.  Laziness does present some challenges for newbies in several ways.  First, developers are not generally conditioned into thinking about whether processing occurs ‘in the provider’ or ‘in the consumer’.  This is often unimportant, but at scale it can become important for efficiency reasons (e.g. generating lots of suspensions/lazy-thunks in memory).  One of the first places that this is likely to be exposed is in discussion around the family of fold functions and which fold is correct in what circumstance.  A second difficulty arises with the subject of infinite data structures, quintessentially lists.  With nothing similar in OO/procedural languages, Haskell can seem a little mysterious.  One of the biggest challenges of laziness-by-default however is the differences it causes in terms of reasoning about time and space.  This is not likely to be an issue that newbies will encounter when they are just in their pure learning phase, but later as they tackle real projects with some scale they are likely to bump into performance issues that will require some additional knowledge of these subtleties.  In this sense, laziness adds some cognitive overhead in the ‘medium term’. 

In summary, I think it's probably true that Haskell has more overheads compared to something like Python, if you're just tackling small projects, unless these overheads have reduced to close to zero due to accrued experience of Haskell and its libraries.  Haskell arguably has features that scale much better for large projects/teams however.  It will be interesting to hear more reports from groups using Haskell at ‘industrial scale’ in the coming years, assuming the language continues to accrete followers.  With the continued and growing challenges in software engineering arising from scale, parallelism and distribution of data and processes, it will also be interesting to see if Haskell is indeed “doomed to succeed”, or whether the current popular engineering languages can evolve to be ‘good enough’ - and therefore maintain their ascendency.  I really hope that a handful of little impediments to using Haskell more broadly in general engineering will get addressed.  Improved tooling is a major theme here, including better Haddock, fixing cabal’s DLL-hell issues, and a full-featured and stable IDE.  Removing more of these unnecessary hurdles still leaves a real learning exercise and some real conceptual displacement for OO developers, but as the benefits become more evident then the motivation should override the learning curve issue.










Monday, October 14, 2013

My Introduction to Monads


Everyone seems to eventually do an "introduction to monads" in their Haskell ramblings.  FWIW, here's my take on it.

A good way to grok monads is to look at the history of the advent of monads in programming - specifically, why and how they were adopted into Haskell.

Haskell is a pure functional language.  That means it is fundamentally about using mathematical functions to build up computation.  Mathematical (pure) functions cannot generate results that are independent in any way of their formal arguments.  Therefore there can be no side-effects, no referencing of state outside of the function and a function that is passed the same argument values on several invocations must always return the same results.  

Pure functions as a basis for programming have huge advantages (though we won't go into these here), but one big disadvantage is this:  the world changes around the program and these changes appear to the program as values that change spontaneously.  Therefore if you want to "readCurrentTemperature" or "getLineOfTextFromConsole" or "readMousePosition", then you would apparently need a function that returned values independent of any inputs it was given.  Taking the console reading example, in Haskell's type language, it would seem that you would want a function:
getLine :: String  -- a function that when called, gets a typed line of text from the console as a String value

It would seem that no arguments would appear to be needed to simply receive text from the console and you would expect to receive the text that user typed on the line.
It's easy to see that in a pure functional world, this is a big problem.  A function with no arguments is a constant - it can return a value sure, but that value cannot change because there are no arguments that could be used to affect the computation of the result.  If we allowed this function to return different results on each call, then it would no longer be a pure function.  This is anathema in Haskell because the impurity would propagate through the whole program and suddenly Haskell would lose all the advantages it gets from guaranteeing that everything in the program definition is pure. 

Another example of this is of course writing to the console.  Here, we might expect to provide a String, the text, which will get written out to stdout or somewhere.  There's nothing particularly interesting that this function might return (other than some success/failure flag, but it's reasonable to assume success in this case).  In Haskell, such a function might be typed:
putStr :: String -> ()
This type expression says that putStr is a function that takes a String and returns a ()… which is called 'unit' and is a value that can carry no useful information.  It's fine to think of unit being the same thing as "void" in the C languages.  In other words, once the text has been written out, there's nothing useful to return from the function.
On the face of it this function isn't so bad as getLine… you could argue that it just happens that all text maps to the same (unit) value - so in isolation it isn't as intrinsically evil as getLine.  Nevertheless it is required to perform a side-effect, and this is completely invisible from the type as we currently have it.  Worse though, is the fact that Haskell reserves the right to optimise away some/any calls to putStr because it knows that it must result in a type that has exactly one value (unit) - i.e. is essentially a function that ignores its input and always returns a constant value.

Aside from the obvious problem with getLine in isolation, another issue comes with combining actions with side-effects like getLine and putStr.  If we want to read a line of text from the console and then output it to the console, we might expect to combine these two actions together into an 'echo' like this:
echo = putStr (getLine) -- get a line of text and then output the string that is obtained
which would then have the type:
echo :: ()
This type says absolutely nothing about the actions that are implied by its definition.  It just says that it results in no useful information!
Moreover, there's a deeper problem.  One of the important things that Haskell is able to do because of its insistence on purity is to reorder function evaluation, as well as sharing and remembering any constant values in the program.  There is nothing in the echo definition that would tell Haskell to always (re)run getLine before running the putStr action (especially if getLine had already been run once and produced a string that looks like it is the only constant output possible from that function!).

By all accounts Haskell languished with the incompatibility of stateful, action-based aspects of programs with its essential, existential requirement for purity for quite a long time in its early development.  Eventually however, Philip Wadler (after reading some discourse on monads in a paper by Eugenio Moggi) made a connection between a mathematical object called a "monad"  and the problem of encapsulating stateful effects in Haskell.  So what is this "monad" thing and why did it appear to solve that problem?

A "monad" (and many would say that it's a shame that we have to use the mathematical name) is simply a object that wraps a value and that allows functions that operate on that inner value to be composed together - BUT those functions must always put the result back into the same kind of wrapper.  This is what creates the encapsulation because:
There's an outer shell around the value, with a distinct type
You can only get at the inner value by using a monadic combinator to convert a function that operates on the inner value into one that operates on the whole monad (and must return a monadic value)
It's possible to completely deny raw access to the inner value by refusing to create a function that simply unwraps the value
It's possible for a given monad to build sequencing of evaluation into the definition of that monad's composition function.  This means you can force the order in which IO operations must be performed, for instance.

Any monad has two main defining functions - these are the functions that any type must declare for itself in order to be a monad:
  1. return - a function to wrap an inner value with the monad type 'wrapper'.  This has the type:  a -> m a.  You could also say that return lifts a value into the monad.
  2. bind - a function to compose some transformation on the inner value with access and re-wrapping in a monadic type.  This has the type:  m a -> (a -> m b) -> m b
With these two, you can define a monadic type and provide the means to make new monadic values of this type (wrapping other values 'inside') and the ability to apply functions to the inner value - but only so that the result is another monadic value of the same type. 

What does it mean to have in 'inner' value and a wrapper?  Well this happens all the time.  Consider Haskell's Maybe type for instance.  This is Haskell's type for adding a type-safe null value to any other type.  The general type is Maybe a, so for a String value, this would be Maybe String.   The inner type (payload) here then would be a String, while the wrapper is the Maybe.  The outer type provides some extra functionality - in this case Maybe adds the one extra value "Nothing" that the value might represent if it doesn't actually hold a value of type String.  The Maybe type predates monads in Haskell, but it illustrates the structural wrapping of a value in a simple way.  

So, back to the the initial motivating problem of IO operations...  

Wadler realised that these features of a monad were completely appropriate and transformative for the "IO problem".
All IO (reading, writing, input, output, etc.) can be encapsulated by the IO monad.  This monad's values describe IO actions that can be performed at some time in the future.  These IO actions can be composed together with the IO monad's bind operator in order to create more complex IO actions from more basic ones.  However, the result is always an IO action value.  Not only does this mean that any code that performs IO is 'honest' about this in its type, but it also keeps all IO bound up inside the IO monad and clearly separated from any pure code.  The IO value itself remains completely pure.  Furthermore, the IO monad forces IO operations to be performed in the strict sequence that is intended.

So, looking at the problematic getLine and putStr functions, getLine would now have the type:
getLine :: IO String -- a function whose return value represents an IO action that will produce a String 

and putStr will have the type:
putStr :: String -> IO ()  - a function that creates an IO action (returning nothing of interest) when provided with a String to output

How do you combine these together to make our little echo program?  
Well, now you can use the IO monad's bind function.  Recollect this has the type m a -> (a -> m b) -> m b
If the first argument of bind is getLine (with type IO String) the "m" will be IO and the "a" will be Strring.  This specializes the bind to be:  IO String -> (String -> IO b) -> IO b
The second argument fits the type signature of putStr, making the "b" into ().  So we can write the echo program as:
echo = bind getLine putStr
… or with Haskell's operator form of bind (>>=) we can write:
echo = getLine >>= putStr
… where bind has been specialized to the type:  IO String -> (String -> IO ()) -> IO ()
… and the type of echo (which is the result of bind, the last component of the type above) is therefore just IO ()

We are free to continue binding more IO operations onto echo to chain together even more IO operations.  For instance:
twoEchos = echo >> echo
will just perform one echo operation (getting a line and writing it out) and then another.  By the way >> is like >>= (bind) except that it doesn't use a result from the first monadic value in the production of the resulting monadic value.  That's needed here because echo doesn't take an argument and only produces an inner value of (), which we don't need for anything as it represents 'void'.

So, if we create a big conglomerate IO action by combining lots of smaller actions, when does the IO actually get done?  Well, the performing of the IO only starts when the Haskell program is run.  The top level of a Haskell program is its "main" function which is typed as "IO ()" - so the entry point of a Haskell program is an IO action itself.  Haskell will start performing the contents of any IO actions that are composed up to the main function and the specific definition of the bind operator defined for the IO monad will ensure that the actions are executed precisely in the order that was intended by the program.

The IO monad was a huge success for separating IO operations in Haskell from pure code, but other monads are also used to separate stateful effects and/or enforce sequential execution.  For example the State monad allows arbitrary state to be collected and maintained by a program, the Writer monad allows log-like actions to be emitted by code at various points, the STM monad defines transactions and the MonadPlus monad describes branching computations that generate values.

As a programming idiom, monads not only offer an encapsulation of values, but also a way to create embedded domain languages right in Haskell.  Any functions that can operate on values inside a specific monad must declare the monad they operate over in their types and only functions 'in' the same monad will compose directly together.  Of course, the inner value can remain polymorphic so monads can work like an interface.  

Monads are so successful and prevalent in Haskell that the language has grown special syntax to make monadic composition (e.g. bind/>>= and anonymousBind/>>) more convenient.  This is the so-called "do notation" and consists of the keyword "do" followed by a block of 'actions' that will be combined with bind or anonymousBind.  The echo function could be written this way with do notation:

echo = do
lineText <- getLine
putStr lineText

The "do notation" is sometimes called Haskell's embedded imperative language, as it resembles the 'top to bottom' style of programming of other languages.  

So, that's my quick introduction to monads.  For some reason monad 'introductions' are often seem very convoluted.  Some people want to talk about the category theory from where the concept was derived and imported into Haskell, but that's an irrelevancy for most people.  Most people just need to know that it's an encapsulation that preserves the outer wrapping type and allows operations on the inner value to be chained together.  Put like that, you are quite likely to have seen monads as a pattern before used for different purposes in different languages… you just didn't know there was an awkward mathematical name for them :-)

Postscript:
Monads seem to have been the subject of quite a few "me too" discussions and implementations in a range of other languages recently (Java, Ruby, Javascript, Python etc.).  That's probably mostly a bit of a meme thing, due to the exotic name.  It would be nice if the importance of composability came to the fore much more in the industry and certainly the monadic pattern is an important way to have encapsulation and composability.  

Nevertheless, the real issues arguably lie with the problems of shared mutable state in software and the features that languages may or may not have to limit side-effects and handle change in a rational way.  Concurrency and distribution of computing are both looming issues that we're struggling to deal with, aside from creating more options that developers must learn to wield effectively.  In transitioning common languages from a state of being extremely unfit for these new challenges to at least offering some solutions, we are possibly creating quite a mess of patterns, idioms, libraries and folklore which we expect teams of developers to apply with necessary correctness and consistency.  

While Haskell may not be the answer to all of this in the end, it does have some fundamental properties that address these issues head on.  Indeed purity and laziness (with purity being the most important) look increasingly essential when code has to be analysed, decomposed, transmitted and evaluated in multiple cores or locations; especially as the complexity of sequence and coordination has to go somewhere.  Patterns like monads were essential in Haskell to make the language pragmatic when it already had some of the fundamentals right, whereas we see other languages adopting feature after feature (e.g. lambdas/closures, monads, actors etc) as cool ideas when they still haven't put their houses in order in other more fundamental ways.  In other words, monads (or a similar thing like arrows) are essential to Haskell, whereas they are merely perhaps just a fun pattern and some 'good practice' in other languages.  

One reason that's cited as being why the world doesn't just adopt Haskell, given that it seems to otherwise be such a good fit for the emerging new challenges, is that it has some cognitive overhead.  It's fascinating, to me at least, to ponder whether this overhead comes from training away from Haskell's concept space when developers are learning the ropes, or whether there are some essential features that are just genuinely harder to grok (when you strip away the boring issues of positioning and nomenclature) than using the current popular stock of languages.  I may ponder on that some more in a future blog post.

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. 

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.