11
\$\begingroup\$

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"
\$\endgroup\$
11
\$\begingroup\$

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
\$\endgroup\$
10
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.