Skip to content
December 9, 2007 / cdsmith

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.

About these ads

6 Comments

Leave a Comment
  1. Abz / Dec 9 2007 12:05 pm

    Massive

  2. cdsmith / Dec 9 2007 12:09 pm

    Abz wrote:

    Massive

    Umm… huh?

  3. Bca / Dec 9 2007 5:34 pm

    Sturdy

  4. Vlad Dogaru / Dec 11 2007 3:35 am

    I’m finding learning Haskell difficult because of monads. Your example helped. Thanks!

  5. Idetrorce / Dec 15 2007 6:31 pm

    very interesting, but I don’t agree with you
    Idetrorce

Trackbacks

  1. Haskell, Eight Queens puzzle « Komap’s Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 80 other followers

%d bloggers like this: