Monday, September 3, 2012

A little strictness goes a long way

In a previous post, I argued that Haskell isn't always lazy because you can control strictness of data types and functions. Today I will show a little example that shows how strictness can be used to avoid problems associated with too much laziness. The good part is that you often only need a little strictness.

When implementing an two-player board game, I had to represent the board pieces and moves. For presentation purposes, let us consider Chess moves; a first aproach is to represent a move as a pair of algebraic coordinates, which in turn are pairs of column and row:

type Move = (Coord, Coord)  -- from, to
type Coord = (Char, Int)    -- column, row

For example, the king pawn opening move is represented by (('e',2),('e',4)).

The problem with this is that pairs are non-strict, and therefore the Move type is inhabited by partially defined moves, e.g.:

(bottom, bottom)  :: Move
(('e',2), bottom) :: Move
(bottom, ('e',4)) :: Move
(('e',2), ('e',bottom) :: Move

(where bottom is some expression that either fails to terminate or throws an exception).

We can rule out all these partially defined moves simply by declaring data types with strict components:

data Move = MkMove !Coord !Coord   -- from, to
data Coord = MkCoord !Char !Int    -- column, row

The advantage of the second representation is that if any of the arguments of MkMove or MkCoord is bottom then the result is also bottom, e.g.:

MkMove bottom bottom  = bottom
MkMove (MkCoord bottom 2) (MkCoord 'e' 4) = bottom 

Why is this important in practice? I can think of at least three advantages:

  1. if your code is buggy and, say, throws an exception when computing move coordinates you will get the error message when the move is constructed rather than when it is used; if your program is going to fail, then it should fail fast;
  2. when writing concurrent or parallel code this ensures that moves are fully evaluated at the right moment, i.e. in the right thread (I stumbled upon this bug when writing a multi-threaded GUI in Haskell);
  3. finally, when compiling with optimization on, GHC will unbox strict data fields which reduces the number of allocations and increases locally; for very inner loops this can be a big performance win.

No comments:

Post a Comment