Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I recently implemented for fun Conway's Game of Life in Javascript (actually coffeescript but same thing). Since javascript can be used as a functional language I was trying to stay to that end of the spectrum. I was not happy with my results. I am a fairly good OO programmer and my solution smacked of same-old-same-old. So long question short: what is the (pseudocode) functional style of doing it?

Here is Pseudocode for my attempt:

class Node
  update: (board) ->
    get number_of_alive_neighbors from board
    get this_is_alive from board
    if this_is_alive and number_of_alive_neighbors < 2 then die
    if this_is_alive and number_of_alive_neighbors > 3 then die
    if not this_is_alive and number_of_alive_neighbors == 3 then alive

class NodeLocations
  at: (x, y) -> return node value at x,y
  of: (node) -> return x,y of node

class Board
  getNeighbors: (node) -> 
   use node_locations to check 8 neighbors 
   around node and return count

nodes = for 1..100 new Node
state = new NodeState(nodes)
locations = new NodeLocations(nodes)
board = new Board(locations, state)

executeRound:
  state = clone state
  accumulated_changes = for n in nodes n.update(board)
  apply accumulated_changes to state
  board = new Board(locations, state)
share|improve this question
3  
Oblig: youtube.com/watch?v=a9xAKttWgP4 –  Oded Nov 20 '11 at 18:54
    
@Oded that is depressingly over my head. I recognize the basic concepts but only just barely –  George Mauer Nov 20 '11 at 22:04
    
Way over my head too... I just posted it as an example of what a master of a specialized language can do. Call it an inspiration for us all :) –  Oded Nov 20 '11 at 22:05
    
@GeorgeMauer "actually coffeescript but same thing" this is sad day –  Raynos Nov 22 '11 at 2:25
add comment

5 Answers 5

up vote 10 down vote accepted

Well, a couple of ideas. I'm not an expert in FP, but...

It's fairly clear we should have a type Board which represents a game state. The basis of the implementation should be an evolve function of type evolve :: Board -> Board; meaning it produces a Board from applying the rules of the game to a Board.

How should we implement evolve? A Board should probably be an n x m matrix of Cells. We could implement a function cellEvolve of type cellEvolve :: Cell -> [Cell] -> Cell which given a Cell and its neighboring Cells calculates the Cell state in the next iteration.

We should also implement a getCellNeighbors function which extracts a Cells neighbors from a Board. I'm not entirely sure of the signature of this method; depending on how you implement Cell and Board you could have for instance getCellNeighbors :: Board -> CoordElem -> CoordElem -> [Cell], which given a Board and two coordinates (CoordElem would be the type used to index positions in a Board), gives you a variable length list of the neighbors (not all cells in the board have the same number of neighbors- corners have 3 neighbors, borders 5 and everyone else, 8).

evolve can thus be implemented by combining cellEvolve and getCellNeighbors for all cells in the board, again the exact implementation will depend on how you implement Board and Cell, but it should be something like "for all cells in the current board, get their neighbors and use them to calculate the new board's corresponding cell'. This should be possible to do with a generic application of those functions over the whole board using a "map over board's cell function".

Other thoughts:

  • You should really implement cellEvolve so that it takes as a parameter a type GameRules which encodes the rules of the game- say a list of tuples (State,[(State,NumberOfNeighbors)],State) which says for a given state and the number of neighbors in each state, which should be the state in the next iteration. cellEvolve's signature could then be cellEvolve :: GameRules -> Cell -> [Cell] -> Cell

  • This would logically take you to making evolve :: Board -> Board turn into evolve :: GameRules -> Board -> Board, so that you could use evolve unchanged with different GameRules, but you could go a step further and make cellEvolve pluggable instead of GameRules.

  • Playing with getCellNeighbors you could also make evolve generic with regards to the Board's topology- you could have getCellNeighbors which wrap around either board's edges, 3d boards, etc.

share|improve this answer
add comment

If you're writing a functional programming version of Life you owe it to yourself to learn about Gosper's Algorithm. It uses ideas from functional programming to achieve trillions of generations per second on boards trillions of squares on a side. That sounds impossible I know, but it is thoroughly possible; I have a nice little implementation in C# that easily handles square boards 2^64 squares on a side.

The trick is to take advantage of the massive self-similarlity of Life boards across both time and space. By memoizing the future state of large sections of the board you can rapidly advance huge sections at once.

I've been meaning to blog a beginners introduction to Gosper's Algorithm for many years now, but I have never had the time. If I end up doing so, I'll post a link here.

Note that you want to look up Gosper's Algorithm for Life computations, not the Gosper's Algorithm for computing hypergeometric sums.

share|improve this answer
add comment

Nice coincidence, we covered this exact problem in our Haskell lecture today. First time I've seen it but here is a link to the source code we were given:

http://pastebin.com/K3DCyKj3

share|improve this answer
    
would you mind explaining more on what it does and why do you recommend it as answering the question asked? "Link-only answers" are not quite welcome at Stack Exchange –  gnat Oct 26 '13 at 22:06
add comment

You might want to look at the implementations on RosettaCode for inspiration.

For example there are functional Haskell and OCaml versions which create a new board each turn by applying a function to the previous one, while the graphical OCaml version uses two arrays and updates them alternately for speed.

Some of the implementations decompose the board update function into functions for counting the neighbourhood, applying the life rule and iterating over the board. Those seem like useful components to base a functional design on. Try modifying only the board, keeping everything else as pure functions.

share|improve this answer
add comment

Here's a short purely functional version in Clojure. All credit goes to Christophe Grand who published this in his blog post: Conway’s Game of Life

(defn neighbours [[x y]]
  (for [dx [-1 0 1] 
        dy (if (zero? dx) [-1 1] [-1 0 1])]
    [(+ dx x) (+ dy y)]))

(defn step [cells]
  (set (for [[loc n] (frequencies (mapcat neighbours cells))
             :when (or (= n 3) (and (= n 2) (cells loc)))]
         loc)))

The game can then be played by repeatedly applying the "step" function to a set of cells, e.g.:

(step #{[1 0] [1 1] [1 2]})
=> #{[2 1] [1 1] [0 1]}

The cleverness is the (mapcat neighbours cells) part - what this does is create a list of eight neighbours for each of the active cells and concatenates them all together. Then the number of times each cell appears in this list can be counted with (frequencies ....) and finally the ones that have the right frequency counts make it through to the next generation.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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