Some Basic Stuff: The Writer Monad

Edit: Clarified some of the code.

Edit II: Comment about laziness.

In this post, Magnus Therning gives a number of solutions to the n-queens problem in Haskell.  The problem is just to arrange n queens on an n x n chess board so that neither is threatening any of the others.  It’s a classic problem that’s solved with backtracking.  That is, you try something, and if it doesn’t work you back up and try something else.  Simple enough.

It reminded me that when I was first learning Haskell, I wrote an n-queens solution using the Writer monad.  This monad just augments the pure functional environment with a new instruction called “tell”.  For those new to Haskell but with some knowledge of Python, consider it equivalent to Python’s “yield”.  Here’s the code:

import Control.Monad
import Control.Monad.Writer
import Data.List

diagonal (x1,y1) (x2,y2) = x1 + y1 == x2 + y2
                        || x1 - y1 == x2 - y2

nqueens n = execWriter $ f [1..n] 1 []
    where f [] _ ps = tell [ps]
          f cs r ps = forM_ cs $ \c ->
                          unless (any (diagonal (r,c)) ps) $
                              f (delete c cs) (r + 1) ((r,c):ps)

And that’s it.  The diagonal function determines if two positions (as order pairs of row and column) are diagonal from each other.  The nqueens function then uses execWriter to run something in the Writer monad and extract the list of answers that were “told” during its execution.  Then I call the workhorse function, which for lack of a better name is just called f.  This function assigns one queen to each row, from the top down.  It is recursive, so it tracks state in its parameters: the first is a list of free columns, the second is the row number, and the third is the list of positions where queens have been placed so far.  If there are no more free columns, then we must have placed all the queens, so we tell the solution.  If there are free columns, we loop through them and try putting a queen in each free column at the current row.

Formally, this returns a list of all solutions to the problem. However, it’s a lazy list; so if you only use the first one, the remainder of the list will never be calculated. So if you only want one solution, just do head (nqueens 8), and you’ll get the first solution.

Okay, nothing phenomenal here.  Just a quick example of some Haskell code.