# Game of Life in Haskell

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"  ## 2 Answers 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


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.