A Haskell implementation of Conway's Game of Life, viewable on the console, no external libs

Question

This is a Haskell implementation of Conway's Game of Life.

It plays on a console. It should be able to play a field of any size, but we only give it a glider on a small field to run at this point.

Using a file named GameOfLife.hs:

import Control.Concurrent
import Text.Printf
main :: IO ()
main = gameOfLife (
 [ [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 , [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 , [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 , [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 , [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 , [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 , [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 , [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 , [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 , [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 ] )

The main function only calls gameOfLife with some startup state - a list of lists of 0s and 1s:

gameOfLife :: [[Integer]] -> IO ()
gameOfLife state = do
 pretty_print state
 let new_state = transition state
 sleep
 printf "\ESC[%dA" $ length state -- move cursor to beginning.
 gameOfLife new_state

First we pretty print the state, define the new state as the transition of the original state, sleep (to slow it down enough to visualize the changes), move the cursor to the beginning using an escape code so we can draw the new state over the old, and then recursively call gameOfLife with the new state.

The pretty print function is as follows - it uses a sprite function to map the 0's and 1's to a viewable field of characters:

pretty_print :: [[Integer]] -> IO ()
pretty_print state = do
 mapM_ print_row state
 where
 print_row linestate = do
 putStrLn $ concat $ map sprite linestate
sprite :: Integer -> String
sprite 0 = "."
sprite _ = "*"

"Sprite," is probably the wrong word. Maybe, "char," would be better?

When printed - it looks like this - here's sample output:

$ ./GameOfLife 
.*..........
..*.........
***.........
............
............
............
............
............
............
............

Then the new state is defined as the transition of the old state.

We start with the row of interest, and get the rows before it and after it. Then we go element by element. When we would get an index that would be out of bounds, I get the index from the other end of the field. This adds some time to the algorithm, I'm sure, but it has the nice effect of allowing the field to wrap around.

-- get new state row by row.
transition :: [[Integer]] -> [[Integer]]
transition state = do
 process 0
 where
 last_i = ((length state) - 1)
 process n = process_row n : (if n == last_i then [] else process (n + 1))
 process_row i = process_rows prev_row this_row next_row
 where
 prev_row = state !! (if i == 0 then last_i else (i - 1))
 this_row = state !! i
 next_row = state !! (if i == last_i then 0 else (i + 1))
 process_rows prev row next = do
 proc 0
 where
 last_j = ((length row) - 1)
 proc m = proc_col m : (if m == last_j then [] else proc (m + 1))
 proc_col j = live_die (row !! j) (
 -- column to left
 (if j == 0 then (last prev + last row + last next) else
 (prev !! (j - 1) + row !! (j - 1) + next !! (j - 1)))
 -- above & below
 + prev !! j + next !! j
 -- column to right
 + (if j == last_j then (prev !! 0 + row !! 0 + next !! 0) else
 (prev !! (j + 1) + row !! (j + 1) + next !! (j + 1)))
 )

The logic for does the cell live or die is if the cell is currently alive, then it stays alive if 2 or 3 surrounding cells are alive, else it dies. If the current cell isn't alive, it only comes to life if there are 3 cells alive next to it. I believe I succinctly cover this logic with pattern matching:

live_die :: Integer -> Integer -> Integer
live_die _ 3 = 1
live_die 1 2 = 1
live_die _ _ = 0

Finally, each transition is followed by some sleeping to avoid having a crazy-looking blur on the screen - I have no problems with the animation with a sleep of 1/10th of a second per transition:

sleep :: IO ()
sleep = threadDelay 100000

I have stack installed, so I built it with:

$ stack ghc GameOfLife.hs

(A friend had to build with ghc -dynamic GameOfLife.hs because he just installed GHC with Arch or Manjaro's package manager, pacman.)

Make the executable file actually executable (only had to do this the first time.)

$ chmod -x GameOfLife

and execute it like so:

$ ./GameOfLife 
.*..........
..*.........
***.........
............
............
............
............
............
............
............

Ideally, the executable could take a value to seed a pseudo-random number generator (PRNG) or a filename with a user-created image. For those goals, I suppose it's obvious that main shouldn't unconditionally start gameOfLife like it does.

Probably the printing should be further separated from the transition.

Maybe we could use data types to represent the cells (0's and 1's) and the field (a list of lists of Integers). But we would need (+) implemented for Cell values.

I think I can see a few other ways to slightly reduce redundant function calls, but I'm not sure I'll save any lines of code that way.

• lehins: Why is it important to have "no external libs"? Using lists whenever you need O(1) indexing is just wrong. You could try using array package instead of lists, which is wired in with ghc, but it is still an external dependency, if you think about.
• Aaron Hall: You have a point, but maybe I don't need O(1) indexing - one answerer did suggest zipping with modified lists. I've been giving this some thought and I wonder if maybe the list of lists representing the field is the wrong paradigm.
• lehins: Even if you do not use indexing, lists are very inefficient unless you are lucky and ghc is able to fuse computation
• Aaron Hall: I was quite proud of getting it to work, but I did not spend much mental energy on reducing algorithmic complexity. What I wonder is if there is a complete reworking of the model that I can factor out and abstract away from the IO handling.
• lehins: don't get me wrong I am not trying to criticise what you've done here. Good job on getting it to work! I am merely suggesting a way you can improve it. Not sure what you mean about abstracting away from IO handling, but good luck with it anyways ;)

Answer 1

Since you haven't specified any focus points, I'll focus on readability.

To speed things up, you may want a Matrix or Vector to represent your board.

transition:

• To make this function more readable, you may want to introduce a more abstract way to address neighbouring fields. For example, a function like

  liveness :: Board -> Position -> Integer
  liveness board pos = sum . filter (isAlive board) . map (addOffset pos) $
   [ (dx,dy) | dx <- (-1,0,1), dy <- (-1,0,1), (dx,dy) /= (0,0) ]
  addOffset :: Position -> Offset -> Position
  addOffset = ...
  isAlive :: Board -> Position -> Bool
  isAlive = ...
  

  that counts the number of living cells surrounding pos.

  Whether addOffset should treat the edge as a border or wrap would be a detail.

• You would like to abstract out explicit recursion in process:

  process n = map process_row [0..length state - 1]
  

• If you have constant-time lookup into your cells, process_row will not need to fetch previous and next rows.

• As an example of the simplicity one could achieve with this part of the code, see Xavier Shay's Game of Life; some things could be improved here, also, but the general game logic is very short and succinct.

main:

• The parenthesis is redundant.

gameOfLife:

• You could abstract out the recursion part so that you have one combinator that performs the meat of the IO operation, and another that iterates it infinitely. That way you could reuse the meat for other versions where a user must interact, or where it only runs a fixed number of iterations:

  stepGame1 :: GameState -> IO GameState
  stepGame1 gameState = do
   prettyPrint gameState
   threadDelay 100000
   printf "\ESC[%dA" (length state) -- move cursor to beginning
   return (transition gameState)
  stepGameInf :: GameState -> IO a
  stepGameInf gameState = stepGame1 gameState >>= stepGameInf
  

  But you could also do it differently; for example, it's a bit weird that stepGame1 both prints and transitions the game state.

For further improvements on the way transitions are computed, you may want to look at:

• Chris Penner's Conway's Game Of Life Using Representable And Comonads, which uses Vector for the game state and comonads; he uses some comonad library tricks (Control.Comonad.Representable.Store) to achieve memoization between transitions.

• The ST monad for efficient, pure transitions without the comonad complexity.

Answer 2

If you want efficient, concise and elegant solution for Game of Life you do want to use an array library instead of resorting to lists. Here is a simple and fast implementation using massiv that automatically parallelizes computation of each intermediate state of game of life. The core feature in this implementation is the lifeStencils. Documentation for massiv stencils is available in the haddock as well as in the readme on github, but I can expend explanation in here a bit as well, if necessary.

You can run it with:

$ clear
$ stack gameOfLife.hs 30 50

Initial state will be randomly generated using splitmix package.

#!/usr/bin/env stack
{- stack --resolver lts-14.0 script --optimize --package massiv --package splitmix --package random -}
module Main where
import Control.Concurrent
import Data.Massiv.Array as A
import Data.Massiv.Array.Mutable.Algorithms (iterateUntilM)
import Data.Word
import System.Environment
import System.Random
import System.Random.SplitMix (initSMGen)
lifeRules :: Word8 -> Word8 -> Word8
lifeRules 1 2 = 1
lifeRules _ 3 = 1
lifeRules _ _ = 0
lifeStencil :: Stencil Ix2 Word8 Word8
lifeStencil = makeStencil (Sz (3 :. 3)) (1 :. 1) $ \ get ->
 lifeRules <$> get (0 :. 0) <*>
 (get (-1 :. -1) + get (-1 :. 0) + get (-1 :. 1) +
 get ( 0 :. -1) + get ( 0 :. 1) +
 get ( 1 :. -1) + get ( 1 :. 0) + get ( 1 :. 1))
life :: Array S Ix2 Word8 -> Array DW Ix2 Word8
life = mapStencil Wrap lifeStencil
printState :: Array S Ix2 Word8 -> IO ()
printState arr = do
 let consCell v acc
 | v == 0 = '.' : acc
 | otherwise = '*' : acc
 A.forM_ (foldrWithin Dim1 consCell "" arr) putStrLn
 putStrLn $ "\ESC[" ++ shows (A.totalElem $ A.size arr) "A"
main :: IO ()
main = do
 [r, c] <- fmap Prelude.read <$> getArgs
 smGen <- initSMGen
 let bool2Word8 b = if b then 1 else 0
 initRandom = compute (bool2Word8 <$> randomArray smGen split random Par (Sz2 r c))
 () <$ iterateUntilM
 (\ _ state _ -> False <$ (printState state >> threadDelay 20000))
 (const life)
 initRandom

Here are some important optimizations that are implemented here:

• Using stencils we get optimal, safe indexing of cells while avoiding bounds checking. Also border checking is handled automatically for us with Wrap
• As mentioned before, computation of next state is performed in parallel
• Because of how iterateUntilM works, during the whole lifetime of the program there are only two arrays ever allocated, therefore it is extremely memory efficient.

• sshine: Strictly speaking, this response isn't code review.
• lehins: @SimonShine the review portion was very concise and simple: do not use lists. But I could not just say that, it would be rude. I had to provide an example how it should be done using arrays.

Answer 3

Naming, the first

Normally haskell is written in camelCase, not under_scores. Up to now, I thought this an arbitrary convention, but I misread

process n = process_row n : (if n == last_i then [] else process (n + 1))
process_row i = process_rows prev_row this_row next_row

as

process n = process_row n : (if n == last_i then [] else process (n + 1))
process row i = process_rows prev_row this_row next_row

in this context. Do you spot the difference? Just a little underscore vs a space.

(Outer) Core loop

But let's get to the point:

process n = process_row n : (if n == last_i then [] else process (n + 1))

This uses manual recursion and transmits indices. Both are not very haskellish. I cannot eliminate them step by step, but both can be avoided with

*Main> :t zipWith3
 zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]

Try to rewrite the first part of your main loop, i.e. where you iterate over the rows in your transition function. Do it now! Game of life is a very good way to learn and improve your haskell, but the best way to learn is to do it yourself, not read up somebody else's solution. Must of the following points a make are just fillers of lesser importance between progressively added spoilers to a zipWith3 solution.

ZipWith example:

zipWith3 (\a b c -> a ++ b ++ c)
 ["Hello, ", "Good "]
 ["World" , "night "]
 ["!" , "John boy"]
["Hello, World!","Good night John boy"]

Why are indexing and manual recursion not "haskellish"? This does not sound like an argument, right?

• both are error-prone
• both are too verbose
• indexing is slow

zipWith3 spoiler 1

re-use your function process_row like zipWith3 process_row ....

Naming, the second

You are indexing withthis_row = state !! i into a variable (or binding, as haskell programmer might prefer) named state. This is a list (of lists). Lists names have often plural form, I recommend

• world
• board
• lines (shadows a Prelude function)
• rows

or whatever term pops up in your specification.

Another squabble about naming: You have process, process_rows, process_row, proc and proc_col. You are not seriously happy with this, are you? I expect the solution to be broken down in smaller and smaller parts, but this: process_row i = process_rows sounds like you are processing a row by processing (all) rows. I'd call process_rows instead combineAdjacentRows or something like it.

Yes, this is a filler. Stop now and rewrite process now.

zipWith3 spoiler 2

This omits the first and last line zipWith3 process_row state (tail state) (tail (tail state)), and consequently shrinks the world/board of game of life vertically, but can be extended into a solution.

Do, do, do

Why didn't you write sleep = threadDelay 100000 as

sleep = do
 threadDelay 100000

Just kidding! You don't need it. There are a lot of dos in your case that you don't need either. Especially those in transition are unnecessary. I do not want to dive too deep, but until you understand monads use do only in context of IO () respectively IO a.

zipWith3 solution

Add the last row of state in front the state. (See how much better with would read with board?), then the plain state lines, finally all lines except this first plus the first line like this:

transition state = zipWith3 process_rows (last state:state) state (tail state ++ state)
 where
 process_rows prev row next = -- (unchanged)

There is more to do, but no complete rewrite by me today.

• Aaron Hall: I considered zip, but I wanted to avoid concatenating lists on lists - seems like a bad idea in Haskell given their immutability.