Haskell track: assignment 5: comprehending monads

Goals

To learn how to use monads in a non-I/O-related context.

Language concepts covered this week

Reading

There are many excellent monad tutorials on the web. I particularly like All About Monads and Monads for the Working Haskell Programmer. Nevertheless, prepare to spend a lot of time before you fully understand what monads have to offer and how they work.

Program to write

This week, we will be doing a version of the triangle game, described in lab 4 of the CS 11 C track. Before doing this lab, you should read the C track lab 4 description so you know what the triangle game is and how to play it. Note that we will use zero-based indexing for the pegs, so the pegs range from peg 0 through peg 14.

Since this is an advanced track, we will solve a more difficult problem than the C programmers had to contend with. Instead of finding one solution to the triangle game problem, we will find all of the solutions starting from a board which only has the center peg (peg 4) missing. A solution is defined as a distinct ordered list of moves leading from the starting configuration to a configuration with only one peg left on the board. There are a large number of these solutions. However, since Haskell is an advanced language, the amount of code you will need to write will be surprisingly small.

You will be provided with a template file containing some of the more obvious code you need for this program. Your job will be to fill in the rest of the code. If you feel that you can come up with a better representation of the problem than the one provided, you are free to change it. I am also supplying the names and type signatures of the functions I used to solve the problem, along with the length in lines of each function not supplied. You may follow my lead or use functions of your own devising. You are also provided with a Makefile which will generate an optimized stand-alone executable.

Your program should compute all solutions of the triangle game, print out the total number of solutions, and print out one solution in detail. The detailed solution will consist of all boards involved in the solution in order starting from the initial board, interleaved with a printout of the moves that led from one board to another. Thus, the printout should list starting board, move, board, move, ... final board. Your program should also tally the number of solutions that end in any particular peg e.g. peg 0, peg 1, peg 2, ... peg 14 and print out the tally for all pegs. Use an array ranging from 0 to 14 to hold the counts. We'll talk more about arrays in class.

You should use monadic style throughout where appropriate. This problem is very easily solved using the list monad, since making a move conceptually turns a board into a list of resulting boards (one for each valid move that could be made). Note that there is a very direct mapping between list comprehensions and the list monad such that anything that can be expressed as a list comprehension can also be expressed in the list monad. Sometimes it's more convenient syntactically to use list comprehensions, sometimes it's easier to use monads, and sometimes it's equally easy. When in doubt, use monads instead of list comprehensions, because this lab is an exercise to get you familiar with using monads. Monads are much more generally applicable than list comprehensions, so it's good to get used to using them. Use the do notation where appropriate.

In class, we'll talk about the MonadZero and MonadPlus type classes, which lists are instances of. You do not need these for your solution but they may be handy. I used mzero from the MonadZero class in my solution.

Other things

Make sure you edit my comments to reflect your code! Also, remove all the line counts from my comments; those are just to give you a rough guideline of how long the functions ought to be. You don't have to make your functions as short as mine were, but if they're much longer you're probably doing something wrong.

In addition, comment the body of your code! The comments I've supplied just describe what the function does, not how it does it. I want the latter kind of comments too.

To hand in

Your program, which will be in a file called triangle_game.hs.

Supporting files

References