[Haskell-cafe] Game of life in haskell.
jon at ffconsultancy.com
Tue Feb 2 21:04:46 EST 2010
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
> 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.
More information about the Haskell-Cafe