Game of Life in Haskell

Question

I wondering what people think of this game of life. I don't think it is working properly, but I am interesting in what people think of the general design.

module GameOfLife where
import Data.List
--Our types 
type Coord = (Int, Int)
origin = (0, 0)
--Think of an image more like an infinite manifold 
type DiscreteImage a = (Coord -> a)
--Cat is our "out of bounds"
data GamePiece = Alive | Dead | Cat
 deriving(Show, Eq)
type GameBoard = DiscreteImage GamePiece
type TransitionRule = (GameBoard -> GamePiece)
under_population = make_population_transition Alive Dead (<2)
overcrowding = make_population_transition Alive Dead (>3)
birth = make_population_transition Dead Alive (==3)
--Order is not important. Only one transition applies per peice, 
--the others operate like id 
transition_rule :: TransitionRule
transition_rule image = foldl (\image f -> f image) image 
 [
 under_population,
 overcrowding,
 birth
 ] origin
--return a new gameboard that applies the transition rule to every 
--spot on the gameboard
step :: TransitionRule -> GameBoard -> GameBoard
step trans gb = trans . offset gb 
--apply the tranisition rule n number of times
simulate :: Int -> TransitionRule -> GameBoard -> GameBoard
simulate count trans gb = foldl apply_step gb steps where 
 steps = replicate count (step trans)
 apply_step gb s = s gb
--translate the image
offset :: DiscreteImage a -> Coord -> Coord -> a
offset image (offsetX, offsetY) (x, y) = image (offsetX + x, offsetY + y) 
--make a square of coords
square_coords :: Int -> [Coord] 
square_coords radius = [(x, y) | x <- diameter_list, y <- diameter_list] where
 diameter_list = [(negate radius) .. radius]
--return a neighborhood with the center missing
punctured_neighborhood :: Int -> DiscreteImage a -> [a] 
punctured_neighborhood size image = map image $ filter (not . (==origin)) $ square_coords size 
--a little test
main = do 
 let (width, height) = get_bounds test_list
 let board1 = simulate 1 transition_rule test_board
 putStr $ unlines [ unwords [ ppr_peice $ board1 (x, y) | x <- [0..(width -1)]] | 
 y <- [0..(height - 1)]]
test_list = 
 [
 [Alive, Dead, Alive, Dead],
 [Alive, Dead, Dead, Alive],
 [Dead, Alive, Dead, Alive],
 [Dead, Alive, Alive, Alive]
 ]
test_board = image_from_lists test_list Cat
--helpers
population_count = length . filter is_Alive . punctured_neighborhood 1
--does nothing if the origin peice /= from, otherwise test for replacement
make_population_transition from to condition image | image origin == from = 
 if (condition . population_count) image 
 then replace image origin to 
 else image
make_population_transition from to test image | otherwise = image
replace image coord_to_replace value coord = if coord_to_replace == coord 
 then value 
 else image coord
bi f g h x = f x `h` g x
is_Alive Alive = True
is_Alive _ = False
from_Bool True = Alive
from_Bool False = Dead
image_from_lists xs default_value coord@(x, y) = if is_in_bounds1 coord
 then (xs !! x) !! y
 else default_value where
 bounds = get_bounds xs
 is_in_bounds1 = is_in_bounds bounds 
get_bounds xs = if null xs
 then (0, 0)
 else (length xs, length $ head xs)
is_in_bounds (xb, yb) (x, y) = (y < yb && y > -1) && (x < xb && x > -1)
ppr_peice Dead = "O"
ppr_peice Alive = "X"
ppr_peice Cat = "C"

• Petr: Have a look at Evaluating cellular automata is comonadic. Using comonads could nicely simplify the game design.

Answer 1

Refactor's answer is excellent and captures most points. One thing in your code which sticks out is the overuse of if. E.g. consider

get_bounds xs = if null xs
 then (0, 0)
 else (length xs, length $ head xs)

I think

getBounds [] = (0,0)
getBounds xs = (length xs, length $ head xs)

is much clearer. Or this, which looks really strange:

make_population_transition from to condition image | image origin == from = 
 if (condition . population_count) image 
 then replace image origin to 
 else image
make_population_transition from to test image | otherwise = image

You should write

make_population_transition from to condition image 
 | image origin == from && 
 (condition . population_count) image = replace image origin to 
 | otherwise = image

Answer 2

First, arranging your code from top to bottom level or vice versa would make this a little easier to read. Also, Haskell code formatting custom generally uses casing like someThing rather than some_thing.

There are also a few items that could be more simply defined (or not at all):

isAlive = (==Alive)
bi = Data.Function.on
tranisitionRule = foldr (.) [underPopulation, overcrowding, birth]

Consider using Hoogle to check if something already exists so you don't need to redefine it.

I think keeping the rule as a single function without spreading it too thinly over your code would be a good idea. For themain function, try to keep it as uninvolved with the pure code as possible.

On the idea of an infinite board, you should consider using a zipper of some sort. This is a simple data structure that separates another data structure into pieces to allow movement inside, rather than storing a path to the current element and changing that. For example,

toZipper xs = ([],xs)
current (_,x:_) = x
left (x:ls,rs) = (ls,x:rs)
right (ls,x:rs) = (x:ls,rs)
unzipper (ls,rs) = reverse ls ++ rs

These functions operate with a zipper that represents the elements at and beyond the current position and the elements behind the current position as a pair. To represent something that is infinite in one direction is trivial (([],repeat 0), a ray), as would be something that is infinite in two directions ((repeat 0,repeat 0), a line). Of course, this particular zipper can be made safer with Maybe and other things, but I'm just demonstrating the concept.

Hopefully, you can see that this can now be extended to a two-directional infinite zipper of two-directional infinite zippers, effectively giving you a two-dimensional plane! Here is the line and plane, in terms of a point:

line = (repeat point, repeat point)
plane = (repeat line, repeat line)

This pattern can be extended to any number of dimensions, but in the specific case of the Game of Life, the plane should suffice. For the purposes of printing, you can create a 5-tuple zipper along the lines of (untraversed left elements, traversed left elements, current element, traversed right elements, untraversed right elements), so you only print the relevant elements. From what I can glean from your code, the zipper pattern is not unlike what you are doing right now, so it shouldn't be too hard to implement. It's also good to abtract the zipper pattern somehow in another module for future use. Even if your plane won't be infinite, try using a zipper.

I'll think I'll stop here for the sake of length. Please ask questions.