[Haskell-cafe] Game of life in haskell.

[Jon Harrop]

On Tuesday 02 February 2010 23:54:58 Richard O'Keefe wrote:
> I understood the ""simple but not scalable and not particularly fast"
> claim *NOT* as a claim about imperative languages but in context as
> a claim about using two-dimensional arrays of booleans to implement
> Conway's Life.

Fair enough. If you want to model either an infinite board or a very sparse 
one then a sparse data structure will be asymptotically faster. But they 
won't be simpler and asymptotically efficient mutable data structures will be 
faster again.

> One message in this thread has already pointed to a 
> solution (in C) that in effect uses a bit-packed sparse representation
> to achieve high speed.  The point is that that approach takes time (and
> space) per generation proportional to the number of occupied cells,
> not the size of the space, and that is the basis of the "scaling" claim.
> A simple Haskell analogue, which has the right asymptotic cost, would
> be to represent a Life generation by a list of
> 	(row_number, [col_no, ..., col_no])
> pairs in strictly ascending order of row number, where each pair
> contains a list of the numbers of the occupied columns in strictly
> ascending order.  The space is (number of occupied cells * a constant)
> + (number of occupied rows * another constant).  Computing the next
> generation then amounts to a bunch of 3-way merges.

That will be a lot faster than using Map or Set but you're still paying a lot 
for the indirections between cons cells. Mutating an array in-place would be 
significantly faster and no more difficult to code correctly because this is 
such a trivial algorithm.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e