[Haskell-cafe] Game of life in haskell.

[Tony Finch]

On 3 Feb 2010, at 02:04, Jon Harrop <jon at ffconsultancy.com> wrote:
> On Tuesday 02 February 2010 23:54:58 Richard O'Keefe wrote:
>>
>> 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.

Richard's description is pretty much exactly what I had in mind for a  
Haskell version of my C code. The C translates to Haskell so well  
because its data structure is immutable: the new generation is written  
to fresh memory then the old generation becomes garbage. The old  
generation is scanned in the order it is written (albeit by three  
pointers with a row between each one) which is inconvenient for linked  
lists. However the algorithm is symmetrical so it doesn't mind  
processing the universe in alternating directions, so long as the  
rendering code can cope :-) The indirections are less bad than they  
might be because the code will always be following a pointer to an  
adjacent memory location, because of the algorithm's simple allocation  
behaviour. But it'll be about twice as slow as the C equivalent  
because it uses twice the memory.

Efficient mutate-in-place Life algorithms become disgustingly  
complicated before they can beat listlife.

Tony.
-- 
f.anthony.n.finch  <dot at dotat.at>  http://dotat.at/