4
\$\begingroup\$

I am learning F# and implemented Conway's Game of Life as an exercise (There are also other implementations on CodeReview). I have tried to forget all my object-oriented background and practice "functional thinking".

Any feedback is welcome, especially related to alternative (more functional) solutions.

open System [<EntryPoint>] let main argv = let rows = 30 let columns = 30 let size = rows*columns let combine listX listY = [ for x in listX do for y in listY do yield x, y ] let createRandomBoard = let rnd = new Random(10) [1..size] |> List.map (fun x -> if rnd.NextDouble() < 0.2 then 1 else 0) |> List.toArray let board = createRandomBoard let toBoardLine (line : int[]) : string = line |> Array.fold (fun agg i -> agg + (if i = 1 then "X" else ".")) "" let drawBoard () = [0..rows-1] |> List.iter (fun y -> printfn "%A" (board.[y*rows..y*rows+columns-1] |> toBoardLine)) let indexToCoordinates index = (index % columns + 1, index / columns + 1) let coordinatesToIndex (x, y) = (y - 1) * columns + (x - 1) let getLivingNeighboursCount idx = let x, y = indexToCoordinates idx let (minX, maxX) = (if x = 1 then columns else x - 1), (if x = columns then 1 else x + 1) let (minY, maxY) = (if y = 1 then rows else y - 1), (if y = rows then 1 else y + 1) combine [minX; x; maxX] [minY; y; maxY] |> List.filter (fun com -> com <> (x,y)) |> List.map coordinatesToIndex |> List.map (fun x -> board.[x]) |> List.sum let indexToNewState idx = let state = board.[idx] let livingNeigbours = getLivingNeighboursCount idx (if livingNeigbours = 3 || (livingNeigbours = 2 && state = 1) then 1 else 0) let updateState () = [0..size-1] |> List.iter (fun idx -> (Array.set board idx (indexToNewState idx))) while true do Console.Clear(); updateState () drawBoard () System.Threading.Thread.Sleep(200); Console.ReadLine() 0
\$\endgroup\$

2 Answers 2

Reset to default
2
\$\begingroup\$

With only a couple of hours ahead of you in my experience with F#, I find the essence of your code fairly functional, although the graphic output is hard to grasp as it has a lot of flicker.

Below find a gentle review of your code with improvements (or at least another way to do the things) and inline comments. I've tried to improve the graphic output by using colors and a distinct update of the cells only when they change.

let playGOL rows columns = let mutable doContinue = true let size = rows*columns let alive = ConsoleColor.Green // Console colors as cell values instead of int/strings let dead = ConsoleColor.Red let combine listX listY = [ for x in listX do for y in listY do yield x, y ] let board = // create the board directly let rnd = new Random() [| for x in 1..size -> if rnd.NextDouble() < 0.2 then alive else dead |] // Initialize the array directly instead of iterate over a list then converted to array let indexToCoordinates index = index % columns + 1, index / columns + 1 // No need for parentheses let coordinatesToIndex (x, y) = (y - 1) * columns + (x - 1) // Instead of using chars I use background colors let updateCell cellIndex state = let x, y = indexToCoordinates cellIndex Console.CursorLeft <- x Console.CursorTop <- y Console.BackgroundColor <- state printf " " Console.BackgroundColor <- ConsoleColor.Black doContinue <- true let drawBoard () = board |> Array.iteri (fun i ch -> updateCell i ch) // Iterate over the board itself instead of a list let getLivingNeighboursCount idx = let x, y = indexToCoordinates idx let minX, maxX = (if x = 1 then columns else x - 1), (if x = columns then 1 else x + 1) let minY, maxY = (if y = 1 then rows else y - 1), (if y = rows then 1 else y + 1) combine [minX; x; maxX] [minY; y; maxY] |> List.filter (fun com -> com <> (x,y)) |> List.map (fun x -> board.[coordinatesToIndex x]) // Map directly from coordinates to value |> List.sumBy (fun x -> if x = alive then 1 else 0) let indexToNewState idx = let state = board.[idx] let livingNeighbours = getLivingNeighboursCount idx if livingNeighbours = 3 || livingNeighbours = 2 && state = alive then if state <> alive then updateCell idx alive // Instead of opdating the whole board just update the changed cell alive else if state <> dead then updateCell idx dead // Instead of opdating the whole board just update the changed cell dead let updateState () = doContinue <- false board |> Array.iteri (fun idx state -> (Array.set board idx (indexToNewState idx))) // Use the board itself to iterate over drawBoard() while doContinue do updateState () System.Threading.Thread.Sleep(100); Console.ReadLine() |> ignore let go() = let size = 40 Console.WindowHeight <- size + 5 Console.WindowWidth <- size + 5 playGOL size size

That said I think both solutions suffer from a generation problem (I'm not a GOL-expert so I may be wrong):

enter image description here

As the image shows getLivingNeighboursCount() checks against two different generations because the board cells are successively updated through the calls to Array.set in updateState() resulting in a false new state. The solution is to create a new board per generation and recursively check those while creating the next generation board:

let playGOL rows columns = let size = rows*columns let alive = ConsoleColor.Green // Console colors as cell values instead of int/strings let dead = ConsoleColor.Red let combine listX listY = [ for x in listX do for y in listY do yield x, y ] let indexToCoordinates index = index % columns + 1, index / columns + 1 // No need for parentheses let coordinatesToIndex (x, y) = (y - 1) * columns + (x - 1) // Instead of using chars I use background colors let updateCell cellIndex state = let x, y = indexToCoordinates cellIndex Console.CursorLeft <- x Console.CursorTop <- y Console.BackgroundColor <- state printf " " Console.BackgroundColor <- ConsoleColor.Black let drawBoard board = board |> Array.iteri (fun i ch -> updateCell i ch) // Iterate over the board itself instead of a list let getLivingNeighboursCount idx (board: ConsoleColor[]) = let x, y = indexToCoordinates idx let minX, maxX = (if x = 1 then columns else x - 1), (if x = columns then 1 else x + 1) let minY, maxY = (if y = 1 then rows else y - 1), (if y = rows then 1 else y + 1) combine [minX; x; maxX] [minY; y; maxY] |> List.filter (fun com -> com <> (x,y)) |> List.map (fun x -> board.[coordinatesToIndex x]) // Map directly from coordinates to value |> List.sumBy (fun x -> if x = alive then 1 else 0) // Replaced according to JanDotNet's comments // let indexToNewState idx (oldBoard: ConsoleColor[]) newBoard = // let state = oldBoard.[idx] // let livingNeighbours = oldBoard |> getLivingNeighboursCount idx // // if livingNeighbours = 3 || livingNeighbours = 2 && state = alive then // Array.set newBoard idx alive // if state <> alive then // updateCell idx alive // Instead of opdating the whole board just update the changed cell // true // else // false // else // Array.set newBoard idx dead // if state <> dead then // updateCell idx dead // Instead of opdating the whole board just update the changed cell // true // else // false // // let updateState (board: ConsoleColor[]) = // let rec updater bdr = // System.Threading.Thread.Sleep(100); // let nextBoard = [| for x in 1..size -> alive |] // let allResults = bdr |> Array.mapi (fun idx state -> indexToNewState idx bdr nextBoard) // let result = allResults |> Array.tryFind (fun res -> res) // match result with // | Some(true) -> updater nextBoard // | _ -> ignore // updater board let indexToNewState idx (oldBoard: ConsoleColor[]) newBoard = let state = oldBoard.[idx] let livingNeighbours = oldBoard |> getLivingNeighboursCount idx let newState = if livingNeighbours = 3 || livingNeighbours = 2 && state = alive then alive else dead Array.set newBoard idx newState if newState <> state then updateCell idx newState true else false let updateState (board: ConsoleColor[]) = let rec updater bdr = System.Threading.Thread.Sleep(100); let nextBoard = [| for x in 1..size -> alive |] let result = bdr |> Array.mapi (fun idx state -> indexToNewState idx bdr nextBoard) |> Array.exists (fun res -> res) match result with | false -> ignore | true -> updater nextBoard updater board let board = // create the board directly let rnd = new Random(10) [| for x in 1..size -> if rnd.NextDouble() < 0.2 then alive else dead |] // Initialize the array directly instead of iterate over a list then converted to array drawBoard board updateState board |> ignore Console.ReadLine() |> ignore let go() = let size = 30 Console.WindowHeight <- size + 5 Console.WindowWidth <- size + 5 playGOL size size
\$\endgroup\$
6
  • \$\begingroup\$ Thanks for the great review! 1.) Your board with the console colors looks really nice ;) 2.) You are absolutely right about the bug with using the state of the updated board to calculating the new state (what a beginner's mistake)... ;). 3) You are using some cool features that i didn't know (e.g. array initializations like[| for x in 1..size -> alive |] or the ignore function) \$\endgroup\$ Commented Feb 8, 2017 at 9:59
  • 1
    \$\begingroup\$ You can replace the large nested if else statement in function indexToNewState with a shorter version by determining newState first. (let newState = ...; Array.set newBoard idx newState; if state <> newState then updateCell idx newState; state <> newState) \$\endgroup\$ Commented Feb 8, 2017 at 11:02
  • \$\begingroup\$ Is there a special reason why you are using Array.tryFind in combination with match result with... instead of Array.exists in combination with if result then updater nextBoard? (e.g. does it help the compiler recognizing tail recursion?) \$\endgroup\$ Commented Feb 8, 2017 at 12:26
  • \$\begingroup\$ @JanDotNet: As for the ugly if statements you are completely right. I knew it was ugle, but I didn't have the time to rethink it properly. As for tryFind vs. exists: exists is much nicer - no good reason for my choice. I took the freedom to update my code with your suggestions. \$\endgroup\$ Commented Feb 8, 2017 at 16:53
  • \$\begingroup\$ instead of board |> Array.iteri (fun i ch -> updateCell i ch) why not just board |> Array.iteri (updateCell)? \$\endgroup\$ Commented Feb 10, 2017 at 13:20
3
\$\begingroup\$

Some remarks :

  • your combine function is in fact List.zip, you might want to explore the Array and List sections of the standard library, they are full of very useful functions that will speed-up your development.

  • createRandomBoard is not a function and thus will always be the same array (arrays being mutable, you might come across some unwanted side effects if you use it twice in the same code). It could be rewritten using Array.init :

    let createRandomBoard () = let rnd = new Random(10) Array.init size (fun _ -> if rnd.NextDouble() < 0.2 then 1 else 0)

  • you are using '0' and '1' to model your two states, why not booleans ? It would eliminate the need for some tests.

  • Array.set ar ind x can be rewritten as ar.[ind] <- x (but, as Foggy Finder said, you would lose some type inference if ar has not been identified as an array before)

  • forms such as :

    [1..n] |> List.iter f

    are indeed functional but inefficient and, I believe, not as readable as using a loop. F# is especially powerful because it is a hybrid language (and not a purely functional one) : don't hesitate to leverage arrays and loops when it makes sense.

\$\endgroup\$
5
  • \$\begingroup\$ let me leave a few comments: \$\endgroup\$ Commented Feb 10, 2017 at 13:12
  • \$\begingroup\$ 1. let rnd = new Random(10) <- sequence will begin with the same value \$\endgroup\$ Commented Feb 10, 2017 at 13:13
  • 1
    \$\begingroup\$ 2. Array.set ar ind x can be rewritten as ar.[ind] <- , well, it can be useful for type inference. \$\endgroup\$ Commented Feb 10, 2017 at 13:15
  • 1
    \$\begingroup\$ Thanks for your feedback! List.zip combines the n'th element of list A with the n'th element of list A. However, my custom combine function combines each element of list A with each element of list B. Therefore it's not the same IMHO (Or do you have special trick in mind? ;)) \$\endgroup\$ Commented Feb 10, 2017 at 16:46
  • \$\begingroup\$ The other tips are helpful... I really like functional programming - but it needs a lot of rethinking. So, thanks for helping :) \$\endgroup\$ Commented Feb 10, 2017 at 16:51

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.