Recently I was surprised by the behaviour of a Haskell program I wrote. This simple example demonstrates the problem:

-- Simple.hs
import System.Environment
main = do
  n <- fmap (read . head) getArgs
  print (length (sequence (replicate n "abc")))

This computes the length of the list formed by every n-sized combination of the letters “a”, “b” and “c”. For example, if n is 4, the first few elements of the list are “aaaa”, “aaab”, “aaac”, “aaba”. (In other words, it’s a slow way to compute 3 to the power of n.) I expected this program to take near-constant space, even though the list might be very long, because it can be consumed by length as it is produced by sequence.

However, as n increases the space required grows exponentially.

This article covers a small part of the internals of Diagrams, a Haskell library for drawing static and animated diagrams. In particular, I give an overview of how a diagram is represented, how paths work, and how attributes are applied to diagrams. The Diagrams library has a lot in it, so not everything can be covered in great detail in such a short article.

Understanding the internals of Diagrams is not necessary for using it effectively – you can make complex diagrams without knowing any of how it works. You might be interested in the internals if you want to extend the library, or add a new rendering backend, or just fix a bug or add documentation. This material might also be of interest to people who want to see examples of type classes, existential types and heterogeneous lists.

The schedule for the International Workshop on Modelling and Reformulation for Constraint Programming is now available.

The submission deadline for the International Workshop on Modelling and Reformulation for Constraint Programming has been extended to 16 July 2012.

Get more information here.

The game Minesweeper is a fun diversion, but even more fun would be to get the computer to solve it for us. I’ve written a basic solver for the version of Minesweeper from Simon Tatham’s excellent Portable Puzzle Collection, called Mines. My solver interacts with the game just like a human player would: by reading the screen’s contents and moving and clicking the mouse.

Here is a video of the solver in action.

The International Workshop on Modelling and Reformulation for Constraint Programming is on again! The submission deadline is 13 July 2012.

Get more information here.

A few months ago, Laurent Vaucher wrote a couple of articles (starting with this one) about solving the puzzle game Hexiom using search algorithms and hand-crafted constraint propagation. It looked like an interesting puzzle, and I was curious about how well a generic constraint solver would perform and how to model the problem. Here I describe how I used MiniZinc and Gecode to tackle it.