DEV Community: Charbel Rami

Statically-typed functional programming, Elm, Conway's Game of Life, and Emergence

Charbel Rami — Mon, 30 Jan 2023 12:02:35 +0000

Statically-typed functional programming, Elm, Conway's Game of Life, and Emergence
- Table of Contents
- Introduction
- Definitions
- Elm syntax
  - Basic types
  - Type aliases
  - Type variables
  - Custom types
  - Functions
  - Conditionals
  - Tuples
  - Records
  - Lists
- Statically-typed functional programming fundamentals
  - Mathematical functions
  - Types
  - Pure functions
  - Determinism
  - Referential transparency
  - Side effects
  - Immutability
  - Monads
    - Maybe
    - Result
  - Higher-order functions
  - Anonymous functions
  - Partially-applied functions
- The Elm Architecture
  - Subscriptions and commands
- Conway's Game of Life
  - Rules
  - Implementation
    - Modeling the universe
    - Initializing the universe
    - Updating the universe
    - Rendering the universe
    - Putting it all together
- Determinism in the Game of Life
- Emergence
- Conclusion
- References
- Acknowledgements
- About the author

Introduction

This is an exploration of implementing Conway's Game of Life in Elm, a statically-typed functional programming language. It is also a demonstration of how statically-typed functional programming can facilitate emergence by allowing for the creation of complex systems through simple rules. For readers unfamiliar with Elm or functional programming, a brief introduction is provided. However, experienced Elm programmers may wish to skip ahead to the section on the Game of Life. The table of contents may be used as a convenient reference for any necessary refreshers.

Definitions

Statically-typed functional programming is a programming paradigm that combines the use of pure functions and immutable data with the use of type systems to ensure the correctness and safety of program execution.

Elm is a statically typed, functional programming language that compiles to JavaScript.

The Conway's Game of Life is a cellular automaton that simulates the evolution of a population of cells in a grid.

Emergence is a phenomenon in which complex patterns and seemingly intelligent behaviors emerge from the interaction of simple entities. This can occur in both natural systems, such as the emergence of complex brain functions from the interaction of neurons in the nervous system, and artificial systems, such as the emergence of traffic patterns in a city from the interaction of individual drivers.

Elm syntax

Elm is statically typed, meaning that the type of each value in the program must be known at compile time, and strongly typed, meaning that the type of each value cannot be changed once it has been declared.

Basic types

In Elm, all values have a type, which can be either a basic type or a composite type. The basic types, known as primitive types, are Int, Float, Bool, Char, and String. For example:

name : String
name =
    "Charbel"


initial : Char
initial =
    'C'


age : Int
age =
    32


favoriteNumber : Float
favoriteNumber =
    3.14


isAccessibilibat : Bool
isAccessibilibat =
    True

Composite types are a combination of one or more basic types. For example:

accessibilibats : List String
accessibilibats =
    [ "Kristine", "Tessa", "Charbel" ]

Ellie

Type aliases

Type aliases allow us to give a new name to an existing type. For example:

type alias Name = String
type alias Age = Int

type alias Person =
    { name : Name
    , age : Age
    }

charbel : Person
charbel = { name = "Charbel", age = 32 }

Ellie

Type variables

Type variables are used to define generic types. For example:

identity : a -> a
identity x = x

identity 1 == 1

The function identity is defined to take in a value of any type a and return a value of the same type a. This allows identity to be used with any type of value, as long as the type of the value passed as an argument is consistent with the type of the value returned.

Custom types

Elm also supports custom types, known as algebraic data types, which are defined using the type keyword and consist of a set of constructors. For example:

type Shape
    = Circle Float
    | Rectangle Float Float

area : Shape -> Float
area shape =
    case shape of
        Circle radius ->
            pi * radius ^ 2

        Rectangle width height ->
            width * height

Shape is an algebraic data type that represents two types of geometric shapes: a Circle and a Rectangle.

An algebraic data type is a type that is defined by a set of constructors, each of which may contain zero or more arguments. In the given example, Shape is an algebraic data type with two constructors: Circle and Rectangle.

The Circle type consists of a single field representing the radius of the circle. The Rectangle type consists of two fields representing the width and height of the rectangle.

The function area is defined to take in a value of the Shape type and return a value of the Float type. The function uses pattern matching to determine which type of Shape has been passed as an argument and then calculates the area of the shape accordingly.

Ellie

Functions

Functions are declared using the assignment operator =. The left side of the operator consists of the function name and its parameters, while the right side contains the function's body. For example:

add : Int -> Int -> Int
add x y =
    x + y

greet : String -> String
greet name =
    "Hello, " ++ name ++ "!"

Ellie

Conditionals

Elm also supports if expressions and case expressions, which are used for conditional execution and pattern matching. For example:

type Person
    = Student String Int
    | Teacher String
    | Administrator String


greet : Person -> String
greet person =
    case person of
        Student name age ->
            if age < 18 then
                "Hello, " ++ name ++ "! Welcome to school."

            else
                "Hello, " ++ name ++ "! How are you enjoying your studies?"

        Teacher name ->
            "Hello, " ++ name ++ "! It's great to see you back in the classroom."

        Administrator name ->
            "Hello, " ++ name ++ "! Thank you for all of your hard work and dedication to the school."

Ellie

Tuples

Tuple types are used to represent a fixed-size collection of values of potentially different types. They are defined using parentheses and commas, with the type of each element specified in the type annotation. For example:

type alias Tamagotchi =
    ( String, Int )


feedTamagotchi : Tamagotchi -> Tamagotchi
feedTamagotchi ( name, hunger ) =
    ( name
    , if hunger > 0 then
        hunger - 1

      else
        hunger
    )

Ellie

Records

Record types are used to represent a collection of named values of potentially different types. They are defined using curly braces and the field : type syntax, with the type of each field specified in the type annotation. For example:

type alias Person =
    { name : String
    , age : Int
    }

Lists

Lists are a composite type in Elm, used to represent a series of values of the same type. Lists can be constructed using the [ and ] characters and separated by commas. For example:

strings : List String
strings =
    [ "Kristine", "Tessa", "Charbel" ]


integers : List Int
integers =
    [ 1, 2, 3 ]


customTypes : List Shape
customTypes =
    [ Circle 1, Rectangle 2 3 ]

Lists can also be constructed using the :: operator, also known as "cons". This operator prepends an element to the front of a list. The following three expressions are equivalent:

integers : List Int
integers =
    1 :: [2, 3]

integers : List Int
integers =
    1 :: 2 :: 3 :: []

integers : List Int
integers =
    [ 1, 2, 3 ]

Lists also have a number of built-in functions for manipulating and transforming their contents, such as map, filter, and foldl. For example:

double : List Int -> List Int
double numbers =
    List.map (\x -> x * 2) numbers

double [ 1, 2, 3 ] == [ 2, 4, 6 ]


even : List Int -> List Int
even numbers =
    List.filter (\x -> remainderBy 2 x == 0) numbers

even [ 1, 2, 3 ] == [ 2 ]


sum : List Int -> Int
sum numbers =
    List.foldl (\acc x -> acc + x) 0 numbers

sum [ 1, 2, 3 ] == 6

Ellie

To learn more about the Elm syntax, see the official Elm syntax reference.

Statically-typed functional programming fundamentals

Mathematical functions

Mathematical functions are mappings that associate a set of input values, known as the domain, with a set of output values, known as the range. These mappings are often denoted by the notation f: X -> Y, where X is the domain and Y is the range. A mathematical function is a rule that takes one or more inputs and produces a single output. In other words, a function can be thought of as a machine that takes an input and produces a unique output.

For instance, consider the function f: R -> R, defined by f(x) = x^2. This function takes a single input x, which belongs to the set of real numbers (denoted by R), and returns an output y, also belonging to the set of real numbers. If we provide the input 2, the function returns 4, since 2^2 = 4. The function f is applied to 2 to obtain 4. The process of applying a function to its arguments in order to obtain a result is known as function application.

Types

f(x) = x^2 in Elm is defined as follows:

square : Float -> Float
square x =
    x^2

square : Float -> Float is the type signature of the function square, which indicates that the domain and the range of square are the set of all floating-point numbers, denoted Float. This is equivalent to the mathematical notation f: R -> R.

square is a pure function.

Ellie

Pure functions

A pure function is equivalent to a mathematical function.

A pure function is characterized by determinism.

Determinism

⚠️ Note that the mathematical notation used in this text to illustrate functional programming concepts may not be fully supported by external references, as I have not found any functional programming references that include such notation. However, I have taken care to ensure its accuracy.

Determinism refers to the property of a function in which the output is always the same given the same input. This means that the function will produce the same result every time it is called with the same arguments, regardless of any external state or context. In other words, a deterministic function is one that has no randomness or external dependencies. This can be formally defined as follows:

f(x) = f(x) ∀ x ∈ D, where D is the domain of the function f.

∀ x1, x2 ∈ D, (x1 = x2) => (f(x1) = f(x2)), where D is the domain of the function f.

f(x) = y ∧ f(x) = y' => y = y' ∀ x ∈ D, y ∈ R, y' ∈ R, where D is the domain of the function f and R is the range of the function f.

A pure function is also characterized by referential transparency.

Referential transparency

Referential transparency refers to the property of a function in which the function can be replaced with its result without affecting the behavior of the program. This means that it can be treated as a value, and the program will behave the same way regardless of whether the function is called or its result is used directly. Formally, this can be written as follows:

f(x) = y ∧ f(x) = y' ∀ x ∈ D, y ∈ R, y' ∈ R, where D is the domain of the function f and R is the range of the function f.

Consider the following function, which takes a floating-point number as input and returns the square of that floating-point number as output:

square : Float -> Float
square x =
    x ^ 2

The following expression:

square 3 + 1 == 10

can be replaced with

(3 ^ 2) + 1 == 10

or equivalently

9 + 1 == 10

without affecting the behavior of the program.

This function is both deterministic and referentially transparent, as it always returns the same result given the same input, and can be replaced with its return value without affecting the behavior of the program. It also has no side effects, as it does not modify the state of the program in any way.

Side effects

Side effects refer to any observable changes to the state of a program that are not reflected in the return value of a function or that occur as a result of a function's execution. Specifically, a pure function f with input x and output y is said to have a side effect if the execution of f(x) results in a change in the global state g such that g ≠ g', where g' is the state of the program before the execution of f(x).

Side effects can introduce unintended complexity and unpredictability into the program.

To mitigate the negative impacts of side effects, functional programming languages often employ a number of principles and design patterns, such as immutability and monads.

Immutability

Immutability refers to the property of an object or data structure to remain unchanged over time. In other words, once an object has been created, it cannot be modified in any way.

Mathematically, we can define immutability as follows: given an object x and an operation f that attempts to modify x, the result of applying f to x is a new object y, such that x and y are distinct and x remains unchanged. This can be formally represented as:

f(x) = y, x ≠ y, x' = x, where x' is the value of x before the execution of f(x).

In functional programming languages, immutability is often achieved through the use of immutable data types. These types cannot be modified after they have been created, and any attempt to do so will result in the creation of a new object.

For example, in Elm, the following code creates an immutable string:

greeting : String
greeting =
    "Hello"

If we try to modify the string by concatenating a new string to it, we will actually create a new string object:

modifiedGreeting : String
modifiedGreeting =
    greeting ++ ", how are you?"

In this case, the original string greeting remains unchanged, while modifiedGreeting is a new string that contains the original greeting and the additional text. A better name for modifiedGreeting would be newGreeting.

Ellie

Monads

A monadic structure is a means of abstracting and composing computations that may contain side effects or non-determinism, or computations that may fail or return no result.

Maybe

One particularly useful example of monadic structures is the Maybe type, which represents a computation that may or may not produce a result. In Elm, the Maybe type is defined as follows:

type Maybe a
    = Just a
    | Nothing

This definition establishes the two possible constructors for Maybe values: Just, which wraps a value of type a, and Nothing, which represents the absence of a value.

To illustrate the utility of Maybe, consider the following scenario: we have a list of integers, and we want to find the first even number in the list. However, it is possible that the list does not contain any even numbers, in which case we want to return Nothing.

Here is how we could implement this function in Elm:

findFirstEven : List Int -> Maybe Int
findFirstEven list =
    case list of
        [] ->
            Nothing

        x :: xs ->
            if remainderBy 2 x == 0 then
                Just x

            else
                findFirstEven xs

This function uses pattern matching to examine the given list. If the list is empty, it returns Nothing. If the list is non-empty, it checks the first element to see if it is even. If it is, it wraps the value in a Just constructor and returns it. If it is not, it recursively calls itself on the tail of the list.

Using Maybe in this way allows us to concisely express the idea that a computation may or may not produce a result, without the need for error handling or exceptions.

For example, suppose we have a function that takes an integer as an input and returns a string indicating whether the integer is even or odd:

stringify : Int -> String
stringify int =
    if remainderBy 2 int == 0 then
        String.fromInt int ++ " is even"

    else
        String.fromInt int ++ " is odd"

We can then use this function to stringify the result of our findFirstEven function, like so:

findAndStringify : List Int -> Maybe String
findAndStringify list =
    findFirstEven list
       |> Maybe.map stringify

The function Maybe.map applies a given function to a value that is wrapped within the Maybe constructor, provided the constructor is of the Just type. If the Maybe value is a Nothing constructor, Maybe.map will return Nothing without applying the function.

Ellie

Result

Another example of a monadic structure in Elm is the Result type, which represents the result of a computation that may either succeed or fail. This type is defined as follows:

type Result error value
    = Ok value
    | Err error

The Result type has two constructors: Ok and Err. The Ok constructor represents a successful computation, and is used to wrap the value that was computed. The Err constructor represents a failed computation, and is used to wrap the error value that was produced.

To use the Result type, we can define a function that performs some computation and returns a Result value. For example, suppose we have a function divide that takes two integers and returns their quotient, but only if the denominator is non-zero:

divide : Int -> Int -> Result String Int
divide numerator denominator =
    if denominator == 0 then
        Err "division by zero"

    else
        Ok (numerator // denominator)

The divide function returns a Result value, which we can pattern match on to handle the success and failure cases. For example, we might use the divide function as follows:

case divide numerator denominator of
    Ok result ->
        "The result is: " ++ String.fromInt result

    Err error ->
        "An error occurred: " ++ error

In this example, if the divide function is called with a non-zero denominator, it will return an Ok value, containing the quotient of the two numbers. If the denominator is zero, it will return an Err value, containing an error message.

Ellie

Higher-order functions

A higher-order function is a function that takes one or more functions as arguments, or returns a function as a result.

In Elm, a simple example of a higher-order function is the List.map function, which takes a function and a list as arguments, and applies the function to each element of the list, returning a new list with the transformed elements. For instance, the following code applies the function double to each element of the list [1, 2, 3], returning a new list [2, 4, 6]:

double : Int -> Int
double x =
    x * 2


doubleList : List Int
doubleList =
    List.map double [ 1, 2, 3 ]

Another example is the List.filter function, which takes a predicate function and a list as arguments, and returns a new list with only the elements that satisfy the predicate. For instance, the following code filters the list [1, 2, 3] to only include even numbers, returning a new list [2]:

isEven : Int -> Bool
isEven x =
    remainderBy 2 x == 0


evenList : List Int
evenList =
    List.filter isEven [ 1, 2, 3 ]

Higher-order functions enable the creation of abstractions, allowing us to define complex operations in terms of simpler ones. They also allow for the creation of functions that are customized for specific purposes, through the use of anonymous functions or partially-applied functions.

Ellie

Anonymous functions

An anonymous function, also known as a lambda function, is a function that is not bound to a specific name.

In Elm, anonymous functions are defined using the \ character. For instance, the following code defines an anonymous function that doubles its argument:

List.map (\x -> x * 2) [1, 2, 3]

returning the list [2, 4, 6].

Partially-applied functions

A partially-applied function is a function that has had one or more of its arguments fixed to specific values. This results in a new function that takes fewer arguments and is a specialization of the original function.

Mathematically, given a function f(x, y, z) and fixed values a, b, we can create a partially-applied function g(z) = f(a, b, z). This new function g is a specialization of f that always applies the values a and b to the first and second arguments of f, respectively, and allows the third argument to vary.

For instance, the following code defines a function doubleList that doubles each element of a list:

doubleList : List Int -> List Int
doubleList =
    List.map (\x -> x * 2)

doubleList is a partially applied function that takes a list as its argument and returns a new list with each element doubled by applying the function (\x -> x * 2) to each element of the input list. We can then use this function to double the elements of any list:

doubleList [1, 2, 3]

Ellie

The Elm Architecture

At its core, the Elm architecture consists of three main components: the model, the view, and the update function.

The model is a representation of the state of the application. It is immutable and can only be updated through the update function.

The view is a function that takes the model as input and returns a representation of the model as HTML.

The update function takes the current model and a message as input, and returns a new model as output.

The architecture follows a predictable pattern of flow, known as the "update loop". This loop begins with the model, which is passed to the view function as an argument. The view function then returns a representation of the model's state as HTML. When the user interacts with the interface, the update function is called, passing the current model state and the user input as arguments. The update function then produces a new model state, which is passed back to the view function and the cycle begins anew.

To learn more about the Elm architecture, see the Elm Architecture section of the official Elm Guide.

Subscriptions and commands

Elm also includes subscriptions and commands.

Subscriptions are functions that are used to handle continuous or asynchronous inputs, such as timers or global event listeners. Subscriptions are used to update the model in response to these events.

Commands are a way for an Elm program to execute side-effects, such as making HTTP requests or generating random numbers.

To learn more about commands and subscriptions, see the Commands and Subscriptions section of the official Elm Guide.

Here is an application that keeps track of the number of seconds that have elapsed since the application started:

⚠️ Caveat: This is not recommended for the creation of an accurate clock in Elm. Ticks and intervals can be affected by the workload of the event loop. Instead, it is recommended to retrieve the current time from the browser and track the difference in seconds.

module Main exposing (..)

import Browser
import Html exposing (..)
import Time

{- The main function is the entry point of the application. It is
responsible for initializing the application and connecting it to the
DOM. -}

main =
    Browser.element
        { init = init
        , view = view
        , update = update
        , subscriptions = subscriptions
        }

{- The Model type is used to represent the state of the application.
In this case, the Model type has a single field, `seconds`, which
represents the number of seconds that have elapsed since the
application started. -}

type alias Model =
    { seconds : Int }

{- The init function is responsible for initializing the application.
In this case, the init function returns a Model with a `seconds` field
initialized to 0, and a `Cmd.none` value, which represents a command
that does nothing. -}

init : () -> ( Model, Cmd Msg )
init _ =
    ( Model 0, Cmd.none )


{- The Msg type is used to represent all possible messages that the
application can receive. In this case, the only message that the
application can receive is a `Tick` message, which is sent by the
`Time` module every second. -}

type Msg
    = Tick Time.Posix


{- The update function is responsible for updating the application's
model in response to a message. In this case, the update function
receives a `Tick` message and increments the `seconds` field of the
model by 1. -}

update : Msg -> Model -> ( Model, Cmd Msg )
update msg model =
    case msg of
        Tick _ ->
            ( Model (model.seconds + 1), Cmd.none )

{- The subscriptions function uses the `Time` module to send a `Tick`
message every second. -}

subscriptions : Model -> Sub Msg
subscriptions _ =
    Time.every 1000 Tick

{- The view function is responsible for rendering the application's
model as HTML. In this case, the view function renders the `seconds`
field of the model as text. -}

view : Model -> Html Msg
view model =
    text ("Seconds: " ++ String.fromInt model.seconds)

Ellie

Conway's Game of Life

Rules

According to Wikipedia, the rules are as follows:

The universe of the Game of Life is an infinite, two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead (or populated and unpopulated, respectively). Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

Any live cell with two or three live neighbours lives on to the next generation.

Any live cell with more than three live neighbours dies, as if by overpopulation.

Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

These rules, which compare the behavior of the automaton to real life, can be condensed into the following:

Any live cell with two or three live neighbours survives.

Any dead cell with three live neighbours becomes a live cell.

All other live cells die in the next generation. Similarly, all other dead cells stay dead.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed, live or dead; births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick. Each generation is a pure function of the preceding one. The rules continue to be applied repeatedly to create further generations.

For clarity, we will emphasize the following terms:

The universe of the Game of Life is an infinite, two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead (or populated and unpopulated, respectively). Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

...

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed, live or dead; births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick. Each generation is a pure function of the preceding one. The rules continue to be applied repeatedly to create further generations.

Implementation

The implementation involves modeling the universe, setting up a way to advance the generations, updating the state of the universe, and rendering the universe as HTML.

Modeling the universe

We begin by modeling the state of the universe, which comprises a grid of cells and the current generation. This can be represented as a record type, with a grid field and a generation field:

type alias Model =
    { grid : Grid, generation : Generation }

The grid of cells is a two-dimensional structure representing the spatial arrangement of cells in the universe. We can think of the grid as a list of rows, where each row is a list of cells:

type alias Grid =
    List (List Cell)

Cell is a custom type, which allows us to define a fixed set of values to represent the possible states of a single cell within the grid, specifically either Live or Dead. By using a custom type, we can ensure that the cells are always in a valid state:

type Cell
    = Live
    | Dead

Initializing the universe

Next, we define the initial state of the universe in the init function:

init : () -> ( Model, Cmd Msg )
init _ =
    ( { grid =
            [ [ Dead, Dead, Dead, Dead, Dead ]
            , [ Dead, Dead, Live, Dead, Dead ]
            , [ Dead, Dead, Dead, Live, Dead ]
            , [ Dead, Live, Live, Live, Dead ]
            , [ Dead, Dead, Dead, Dead, Dead ]
            ]
      , generation = 0
      }
    , Cmd.none
    )

Here, we use a tuple to return the initial state of the universe along with an empty command, as we do not need any effects to be performed. This is required by the init function, which, when not used in sandbox mode, must return a tuple of type ( model, Cmd msg ).

To learn more about the init function, refer to the Browser package documentation.

Updating the universe

We define a custom type, Msg, to represent the possible messages that can be sent to the application. In this particular case, we only have one message, Tick, which is sent at regular intervals to advance the generations:

type Msg
    = Tick Time.Posix

We implement the subscriptions function, which uses Time.every to set up a timer that sends Tick messages at regular intervals of 200ms:

subscriptions : Model -> Sub Msg
subscriptions _ =
    Time.every 200 Tick

We implement the update function, which takes a message and the current state of the universe and returns a new state. In this case, we only have one message, Tick. We define the nextGenerationGrid and nextGenerationCell functions, which will be used to compute the state of the next generation:

update : Msg -> Model -> ( Model, Cmd Msg )
update msg model =
    case msg of
        Tick _ ->
            ( { grid = nextGenerationGrid model.grid, generation = model.generation + 1 }, Cmd.none )


nextGenerationGrid : Grid -> Grid
nextGenerationGrid grid =
    List.indexedMap (\i row -> List.indexedMap (\j cell -> nextGenerationCell ( i, j ) cell grid) row)
        grid


nextGenerationCell : ( Int, Int ) -> Cell -> Grid -> Cell
nextGenerationCell ( i, j ) cell grid =
    let
        gridLength =
            List.length grid

        countLiveNeighbors =
            List.foldl
                (\( i_, j_ ) acc ->
                    let
                        iMod =
                            modBy gridLength i_

                        jMod =
                            modBy gridLength j_
                    in
                    case List.head (List.drop iMod grid) of
                        Just row ->
                            case List.head (List.drop jMod row) of
                                Just Live ->
                                    acc + 1

                                _ ->
                                    acc

                        _ ->
                            acc
                )
                0

        liveNeighbors =
            countLiveNeighbors
                [ ( i - 1, j - 1 )
                , ( i - 1, j )
                , ( i - 1, j + 1 )
                , ( i, j - 1 )
                , ( i, j + 1 )
                , ( i + 1, j - 1 )
                , ( i + 1, j )
                , ( i + 1, j + 1 )
                ]
    in
    case cell of
        Live ->
            if liveNeighbors < 2 || liveNeighbors > 3 then
                Dead

            else
                Live

        Dead ->
            if liveNeighbors == 3 then
                Live

            else
                Dead

⚠️ Note that the grid of cells in this system is finite, but we treat it as if it were infinite by wrapping around the edges using the modBy function. This means that the cell located immediately to the left of the leftmost cell becomes the rightmost cell, and the cell above the topmost cell becomes the bottommost cell.

Rendering the universe

Finally, we implement the view function, which takes the current state of the universe and returns an HTML view:

view : Model -> Html Msg
view model =
    div []
        [ renderGrid model.grid
        , text ("Generation: " ++ String.fromInt model.generation)
        ]


renderGrid : Grid -> Html Msg
renderGrid grid =
    div [] (List.map renderRow grid)


renderRow : List Cell -> Html Msg
renderRow row =
    div [ style "display" "flex" ] (List.map renderCell row)


renderCell : Cell -> Html Msg
renderCell cell =
    div
        [ style "width" "16px"
        , style "height" "16px"
        , style "border" ".5px solid #ccc"
        , style "transition" "background-color 150ms ease-out"
        , style "background-color"
            (case cell of
                Live ->
                    "#222"

                Dead ->
                    "#fff"
            )
        ]
        []

Putting it all together

Here is the complete code for the simulation:

module Main exposing (..)

import Browser
import Html exposing (..)
import Html.Attributes exposing (style)
import Time


main : Program () Model Msg
main =
    Browser.element
        { init = init
        , view = view
        , update = update
        , subscriptions = subscriptions
        }


type alias Model =
    { grid : Grid, generation : Int }


type alias Grid =
    List (List Cell)


type Cell
    = Live
    | Dead


init : () -> ( Model, Cmd Msg )
init _ =
    ( { grid =
            [ [ Dead, Dead, Dead, Dead, Dead ]
            , [ Dead, Dead, Live, Dead, Dead ]
            , [ Dead, Dead, Dead, Live, Dead ]
            , [ Dead, Live, Live, Live, Dead ]
            , [ Dead, Dead, Dead, Dead, Dead ]
            ]
      , generation = 0
      }
    , Cmd.none
    )


type Msg
    = Tick Time.Posix


update : Msg -> Model -> ( Model, Cmd Msg )
update msg model =
    case msg of
        Tick _ ->
            ( { grid = nextGenerationGrid model.grid, generation = model.generation + 1 }, Cmd.none )


subscriptions : Model -> Sub Msg
subscriptions _ =
    Time.every 200 Tick


nextGenerationGrid : Grid -> Grid
nextGenerationGrid grid =
    List.indexedMap (\i row -> List.indexedMap (\j cell -> nextGenerationCell ( i, j ) cell grid) row)
        grid


nextGenerationCell : ( Int, Int ) -> Cell -> Grid -> Cell
nextGenerationCell ( i, j ) cell grid =
    let
        gridLength =
            List.length grid

        countLiveNeighbors =
            List.foldl
                (\( i_, j_ ) acc ->
                    let
                        iMod =
                            modBy gridLength i_

                        jMod =
                            modBy gridLength j_
                    in
                    case List.head (List.drop iMod grid) of
                        Just row ->
                            case List.head (List.drop jMod row) of
                                Just Live ->
                                    acc + 1

                                _ ->
                                    acc

                        _ ->
                            acc
                )
                0

        liveNeighbors =
            countLiveNeighbors
                [ ( i - 1, j - 1 )
                , ( i - 1, j )
                , ( i - 1, j + 1 )
                , ( i, j - 1 )
                , ( i, j + 1 )
                , ( i + 1, j - 1 )
                , ( i + 1, j )
                , ( i + 1, j + 1 )
                ]
    in
    case cell of
        Live ->
            if liveNeighbors < 2 || liveNeighbors > 3 then
                Dead

            else
                Live

        Dead ->
            if liveNeighbors == 3 then
                Live

            else
                Dead


view : Model -> Html Msg
view model =
    div []
        [ renderGrid model.grid
        , text ("Generation: " ++ String.fromInt model.generation)
        ]


renderGrid : Grid -> Html Msg
renderGrid grid =
    div [] (List.map renderRow grid)


renderRow : List Cell -> Html Msg
renderRow row =
    div [ style "display" "flex" ] (List.map renderCell row)


renderCell : Cell -> Html Msg
renderCell cell =
    div
        [ style "width" "16px"
        , style "height" "16px"
        , style "border" ".5px solid #ccc"
        , style "transition" "background-color 150ms ease-out"
        , style "background-color"
            (case cell of
                Live ->
                    "#222"

                Dead ->
                    "#fff"
            )
        ]
        []

Ellie

Determinism in the Game of Life

Conway's Game of Life is a deterministic system in which the state of a cell in a given generation is exclusively determined by the state of its eight neighbors in the preceding generation. These rules are simple and deterministic, yet they give rise to a wide range of patterns and behaviors, from stable configurations to oscillating patterns to seemingly random behavior. In a functional programming language, pure functions can effectively handle the deterministic nature of the Game of Life, and the behavior of a functional program, which is determined by the composition and application of these functions, can also be complex and varied, even though it is based on simple, deterministic rules.

Emergence

The Game of Life exhibits emergent behavior, which is the result of the interactions between individual cells in the system. This emergent behavior is not directly observable in any individual cell. Instead, it is only observable in the behavior of the system as a whole.

Emergent behavior, or the emergence of complex behaviors from the interactions of individual components, is a common characteristic of many systems. One way to carefully control these interactions is through the use of functional programming and a strong type system.

Functional programming can be used to effectively manage complexity in such systems. Pure functions allow for better understanding of a system's behavior, as the behavior of each function can be evaluated in isolation. In the Game of Life, for instance, we can be confident that the state of a cell will only depend on the state of its neighbors, and that the function will not have any unintended side effects on the rest of the system. Additionally, composition of functions allows for the creation of complex behaviors by combining simpler, easily understood components.

A strong type system helps enforce the control of interactions between individual components by preventing the mixing of incompatible types and providing explicit type annotations that clearly communicate the intended use of each component.

For example, in a system simulating the behavior of a flock of birds, each bird could be represented by an object with certain attributes, such as position and velocity, and certain behaviors, such as the ability to move and change direction. A specific Bird type could be defined with explicit type annotations for each attribute and behavior. This would prevent errors such as trying to add a bird's position to its velocity or trying to call a non-existent behavior on a bird object. Furthermore, explicit type annotations enable developers to more easily understand how the system is intended to work and consider the potential consequences of modifying it.

Conclusion

In summary, Conway's Game of Life is an example of how the use of pure functions and immutable data structures allows for the effective handling of determinism, and how the ability to evaluate the behavior of functions in isolation allows for better understanding of emergent behavior.

Finally, statically-typed functional programming languages significantly improve the reliability of complex systems and make them easier to maintain over time. By providing a clear and explicit structure to the code, these languages make it easier for developers to understand the intent and functionality of a program, leading to code reuse and the introduction of new features without disrupting the overall system.

References

Acknowledgements

Thanks to the accessibilibats and Blake for encouraging me to write this article.

Thanks to Richard for his excellent Elm in Action book, which was an invaluable resource for learning Elm.

Thanks to Kristine, Tessa, and Brian Hicks for their thorough feedback on this article.

About the author

Charbel is an engineer at NoRedInk. Charbel has been dedicated to improving accessibility for students with disabilities since joining NoRedInk and the accessibility team, known as the Accessibilibats, in July 2022, and has truly enjoyed the opportunity to make a positive impact in this area.

If you're interested in learning more about Charbel's work, be sure to follow him on Twitter @charbelrami.

How to optimize shared states in React

Charbel Rami — Tue, 10 Mar 2020 13:57:40 +0000

Consider the following example:

export default function App() {
  const [count, setCount] = useState(0);
  const [toggle, setToggle] = useState(false);

  return (
    <Context.Provider value={{ count, setCount, toggle, setToggle }}>
      <SubtreeComponent>
        <Decrement />
        <Counter />
        <Increment />
        <Toggle />
      </SubtreeComponent>
    </Context.Provider>
  );
}

export const Context = createContext();

export function Counter() {
  const { count } = useContext(Context);

  return <span>{count}</span>;
}

export function Increment() {
  const { setCount } = useContext(Context);

  return <button onClick={() => setCount(prev => prev + 1)}>Increment</button>;
}

export function Decrement() {
  const { setCount } = useContext(Context);

  return <button onClick={() => setCount(prev => prev - 1)}>Decrement</button>;
}

export function Toggle() {
  const { toggle, setToggle } = useContext(Context);

  return (
    <label>
      <input
        type="checkbox"
        checked={toggle}
        onChange={() => setToggle(prev => !prev)}
      />
      Toggle
    </label>
  );
}

codesandbox

(During the profiling sessions, the increment button was clicked)

Intuitively, when we change a context value, we might assume that this change propagates solely to context consumers (components calling useContext) that use this particular value. However, a change in a single value of a context propagates to all its consumers scheduling them to update and re-render regardless of whether they use this value or not. This change also causes the entire subtree wrapped in the context provider to re-render.

Although it may not necessarily result in significant performance issues, except when values change too often or when there are expensive re-render calculations that haven’t been memoized (useMemo), it is more likely to lead to undesirable behavior, particularly when a consumer component fires effects after every render.

Firstly, we want to prevent the context provider subtree from re-rendering unnecessarily. This can be accomplished by passing the provider subtree as a children prop to a wrapper component.

(The context provider subtree is represented by SubtreeComponent for the sake of simplicity)

export default function App() {
  return (
    <Provider>
      <SubtreeComponent>
        <Decrement />
        <Counter />
        <Increment />
        <Toggle />
      </SubtreeComponent>
    </Provider>
  );
}

export function Provider({ children }) {
  const [count, setCount] = useState(0);
  const [toggle, setToggle] = useState(false);

  return (
    <Context.Provider value={{ count, setCount, toggle, setToggle }}>
      {children}
    </Context.Provider>
  );
}

codesandbox

Now, we want to prevent consumers from re-rendering unless necessary, or, more precisely, unless they actually use the changed value. One convenient approach is to create a separate context for each independent value.

export function Provider({ children }) {
  const [count, setCount] = useState(0);
  const [toggle, setToggle] = useState(false);

  return (
    <CountContext.Provider value={{ count, setCount }}>
      <ToggleContext.Provider value={{ toggle, setToggle }}>
        {children}
      </ToggleContext.Provider>
    </CountContext.Provider>
  );
}

export const CountContext = createContext();

export const ToggleContext = createContext();

codesandbox

Note that the consumers rendered nonetheless. This happens because both state variable declarations are in the same parent component. So we should split them into two components.

export default function App() {
  return (
    <CountProvider>
      <ToggleProvider>
        <SubtreeComponent>
          <Decrement />
          <Counter />
          <Increment />
          <Toggle />
        </SubtreeComponent>
      </ToggleProvider>
    </CountProvider>
  );
}

export function CountProvider({ children }) {
  const [count, setCount] = useState(0);

  return (
    <CountContext.Provider value={{ count, setCount }}>
      {children}
    </CountContext.Provider>
  );
}

export function ToggleProvider({ children }) {
  const [toggle, setToggle] = useState(false);

  return (
    <ToggleContext.Provider value={{ toggle, setToggle }}>
      {children}
    </ToggleContext.Provider>
  );
}

codesandbox

State variable declarations return a pair of values, the current state and a function that updates that state. These values can be consumed independently, so we should split them into two contexts.

export function CountProvider({ children }) {
  const [count, setCount] = useState(0);

  return (
    <CountContext.Provider value={count}>
      <SetCountContext.Provider value={setCount}>
        {children}
      </SetCountContext.Provider>
    </CountContext.Provider>
  );
}

export function ToggleProvider({ children }) {
  const [toggle, setToggle] = useState(false);

  return (
    <ToggleContext.Provider value={toggle}>
      <SetToggleContext.Provider value={setToggle}>
        {children}
      </SetToggleContext.Provider>
    </ToggleContext.Provider>
  );
}

codesandbox

So far, so good. But as you may have noticed, this code could rapidly become too long and time-consuming.

react-context-x is a tiny (3kB) library that might come in handy. It provides a familiar API that is basically an abstraction to the code shown in these examples.

Consider an object of all the states we want to share from the same level in the component tree.

const states = {
  count: 0,
  toggle: false
};

createContexts (plural) is a function that receives these states, creates a pair of contexts for each of one, and returns an array with all these pairs.

const states = {
  count: 0,
  toggle: false
};

export const contexts = createContexts(states);

Then, we pass this array to a Providers component that inserts all the required providers into the component tree.

export default function App() {
  return (
    <Providers contexts={contexts}>
      <SubtreeComponent>
        <Decrement />
        <Counter />
        <Increment />
        <Toggle />
      </SubtreeComponent>
    </Providers>
  );
}

To consume these contexts, we use hooks that accept the array as the first argument and, as the second argument, a string that identifies which context we want to access.

export function Counter() {
  const count = useStateContext(contexts, "count");

  return <span>{count}</span>;
}

export function Increment() {
  const setCount = useSetStateContext(contexts, "count");

  return <button onClick={() => setCount(prev => prev + 1)}>Increment</button>;
}

export function Decrement() {
  const setCount = useSetStateContext(contexts, "count");

  return <button onClick={() => setCount(prev => prev - 1)}>Decrement</button>;
}

export function Toggle() {
  const toggle = useStateContext(contexts, "toggle");
  const setToggle = useSetStateContext(contexts, "toggle");

  return (
    <label>
      <input
        type="checkbox"
        checked={toggle}
        onChange={() => setToggle(prev => !prev)}
      />
      Toggle
    </label>
  );
}

codesandbox

Thanks!

Learn more:

Pure Components, Interfaces and Logic Hooks.

Charbel Rami — Wed, 09 Jan 2019 02:52:54 +0000

Available on Medium

This architecture is divisible into three components, Pure Components, Interfaces and Logic Hooks. It is a variant on the Presentational and Container Components pattern described by Dan Abramov, now considering the existence of Hooks.

Pure Components

Interface

Logic Hook

Interfaces are mainly concerned with how information should be shared between Logic Hooks and with Pure Components. Interfaces receive functions and values provided by Logic Hooks and share them with other Logic Hooks or pass them as props to Pure Components.

Logic Hooks are similar to Container Components. Pure Components are similar to Presentational Components. But they differ on some points.

Comparison

Presentational Components and Pure Components

From Dan's post:
"My presentational components:

Are concerned with how things look.
May contain both presentational and container components** inside, and usually have some DOM markup and styles of their own.
Often allow containment via this.props.children.
Have no dependencies on the rest of the app, such as Flux actions or stores.
Don't specify how the data is loaded or mutated.
Receive data and callbacks exclusively via props.
Rarely have their own state (when they do, it's UI state rather than data).
Are written as functional components unless they need state, lifecycle hooks, or performance optimizations.
Examples: Page, Sidebar, Story, UserInfo, List."

My Pure Components:

Same ("Are concerned with how things look.").
May contain other Pure Components, markup, and styles.
Same ("Often allow containment via this.props.children.") props.children.
Same ("Have no dependencies on the rest of the app, such as Flux actions or stores.").
Same ("Don't specify how the data is loaded or mutated.").
Same ("Receive data and callbacks exclusively via props.").
Don't have their own state. They should receive, as props, a local state provided by a Logic Hook through an Interface.
Are written as functional components.
Same ("Examples: Page, Sidebar, Story, UserInfo, List.").

Container Components and Logic Hooks

From Dan's post:
"My container components:

Are concerned with how things work.
May contain both presentational and container components** inside but usually don't have any DOM markup of their own except for some wrapping divs, and never have any styles.
Provide the data and behavior to presentational or other container components.
Call Flux actions and provide these as callbacks to the presentational components.
Are often stateful, as they tend to serve as data sources.
Are usually generated using higher order components such as connect()from React Redux, createContainer() from Relay, or Container.create()from Flux Utils, rather than written by hand.
Examples: UserPage, FollowersSidebar, StoryContainer, FollowedUserList."

My Logic Hooks:

Same ("Are concerned with how things work.").
Shouldn't contain other components, markup or styles.
Provide the data and behavior to Interfaces.
Call Flux actions and provide these as callbacks to Interfaces.
Same ("Are often stateful, as they tend to serve as data sources.").
n/a ("Are usually generated using higher order components such as connect()…").
Examples: useUser, useFollowers, useStory, useFollowed.

Just like the Presentational and Container Component pattern, this separation makes it easier to replace or delete code. If you wanted to replace your state container, you would need to update your Logic Hooks, but not your Interfaces or Pure Components. But it is particularly useful if your application has different UI flows, hence the name "Interface". For example, you could use the same Logic Hooks for a React and React Native application with different Interfaces. These Interfaces would receive information from the same Logic Hooks, and accommodate Pure Components in distinct ways.

DEV Community: Charbel Rami

Statically-typed functional programming, Elm, Conway's Game of Life, and Emergence

Table of Contents

Introduction

Definitions

Elm syntax

Basic types

Type aliases

Type variables

Custom types

Functions

Conditionals

Tuples

Records

Lists

Statically-typed functional programming fundamentals

Mathematical functions

Types

Pure functions

Determinism

Referential transparency

Side effects

Immutability

Monads

Maybe

Result

Higher-order functions

Anonymous functions

Partially-applied functions

The Elm Architecture

Subscriptions and commands

Conway's Game of Life

Rules

Implementation

Modeling the universe

Initializing the universe

Updating the universe

Rendering the universe

Putting it all together

Determinism in the Game of Life

Emergence

Conclusion

References

Acknowledgements

About the author

How to optimize shared states in React

Pure Components, Interfaces and Logic Hooks.

Comparison

Presentational Components and Pure Components

Container Components and Logic Hooks

Full example