3
\$\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\$
1
\$\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\$
  • \$\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\$ – JanDotNet Feb 8 '17 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\$ – JanDotNet Feb 8 '17 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\$ – JanDotNet Feb 8 '17 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\$ – Henrik Hansen Feb 8 '17 at 16:53
  • \$\begingroup\$ instead of board |> Array.iteri (fun i ch -> updateCell i ch) why not just board |> Array.iteri (updateCell)? \$\endgroup\$ – user110704 Feb 10 '17 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\$
  • \$\begingroup\$ let me leave a few comments: \$\endgroup\$ – user110704 Feb 10 '17 at 13:12
  • \$\begingroup\$ 1. let rnd = new Random(10) <- sequence will begin with the same value \$\endgroup\$ – user110704 Feb 10 '17 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\$ – user110704 Feb 10 '17 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\$ – JanDotNet Feb 10 '17 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\$ – JanDotNet Feb 10 '17 at 16:51

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.