[Haskell-cafe] Game of life in haskell.

Serguey Zefirov sergueyz at gmail.com
Tue Feb 2 11:10:05 EST 2010

2010/2/2 Lyndon Maydwell <maydwell at gmail.com>:
> I chose the array mainly for the fast lookup time compared to lists,
> are you suggesting something like creating a "Map (X,Y) Health"? I'm
> not currently updating any structures, rather creating the successor
> from scratch. I can see how the map may work very well for the sparse
> nature of non-early life games now that I think of it.

Because your Health is basically Bool, you can use Set (X,Y) for a set
of live objects.

Creation of new Array is (without knowing some subtle details) is
O(max coordinates difference between live cells). Creation of new Set
(X,Y) is O(NlogN) (N = number of live objects). Most of the cells in
Life are empty, so the Set/Map approach is faster. Also it leads to
very concise code.

Actually, your solution with arrays is the most often occured solution
an imperative programmer will come with. It is simple but not scalable
and not particularly fast.

More information about the Haskell-Cafe mailing list