Tony Finch – blog

The Game of Life is fairly pointless, but in this case it is also written in "point-free" style which minimizes the use of variables. I think it's quite cute.

It's easy to represent an unbounded quarter-plane in Haskell as [[Cell]], i.e. a list of rows of cells - the lists are lazy, so they can make themselves as long as necessary. You can then define the universe without form and void, such that darkness is upon the face of the screen, as:

  data Cell = Dead | Alive
  deadline = repeat Dead
  deadspace = repeat deadline

To create a pattern we add live cells to this substrate. First we need a helper function that changes just the Nth element of a list:

  mapNth n f xs = as ++ f b : cs
    where (as,b:cs) = splitAt n xs

Then to set an individual cell we use mapNth to modify the Xth element of the Yth row. Pointfree style tends to use the $ operator a lot, which makes Perl poetry-style programmers feel at home.

  setcell (x,y) = mapNth y $ mapNth x $ const Alive

We can apply setcell successively starting from dead space to create a pattern. For example, here's a glider set to run off into the unbounded corner of the universe.

  pattern = foldr setcell deadspace
  glider = pattern [(2,1),(3,2),(3,3),(2,3),(1,3)]

When working out the next generation we need to work out the neighbourhood of each cell, i.e. the 3x3 square consisting of the cell and its eight neighbours. We'll end up with the neighbourhood represented as a triple of triples, on which it's straightforward to specify the Game of Life rule:

  fromCell Dead = 0
  fromCell Alive = 1

  rule ((a,b,c),(d,e,f),(g,h,i)) =
      if count == 2 then e else
      if count == 3 then Alive else Dead
    where
      count = sum $ map fromCell [a,b,c,d,f,g,h,i]

The one-dimensional version of the neighbourhood is quite easy, turning a list into a list of overlapping triples.

  by3 (a:b:c:ds) = (a,b,c) : by3 (b:c:ds)
  by3     _      = []

We're going to apply by3 to each row to make horizontal triples, and to the list of rows itself to make triple rows of triples. However what we want is rows of triple triples. Turning a triple of lists into a list of triples is almost what zip3 does, except that zip3 is inconveniently curried.

  uncurry3 f (a,b,c) = f a b c
  zip3' = uncurry3 zip3

Then the code to turn a list of rows of cells into a list of rows of neighbourhoods is just as I outlined in the previous paragraph.

  by3by3 = map zip3' . by3 . map by3

When calculating the next generation, we want to add a strip of empty space to each edge of the universe, so that all our cells have neighbours. If we did not do this the universe would unravel at one cell per generation, a bit like in Greg Egan's book "Schildt's ladder".

  grow = (deadline:) . map (deadcell:)

Now we can actually calculate the next generation! Grow the universe, work out the neighbourhoods, then apply the rule to each of them.

  generate = map (map rule) . by3by3 . grow

To display the universe, we need to convert cells to strings

  instance Show Cell where
    show Dead = "  "
    show Alive = "[]"

To display the whole universe, we need to truncate it to the size of the screen by taking only the necessary elements from the lists, concatenate the string representation of the cells in each row, and join the rows with newlines.

  display (x,y) = unlines . map (concatMap show . take x) . take y

Then the main program simply loops displaying the universe and calculating its next generation.

  loop u = do
    putStrLn $ display (10,10) u
    _ <- getLine
    loop $ generate u

  main :: IO ()
  main = loop glider