Statically-typed functional programming, Elm, Conway's Game of Life, and Emergence
Tags: typed, functional, elm
Published: 2023-01-30 12:02:35

---
title: Statically-typed functional programming, Elm, Conway's Game of Life, and Emergence
published: true
description: 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.
tags: typed, functional, elm
# cover_image: https://direct_url_to_image.jpg
# Use a ratio of 100:42 for best results.
# published_at: 2023-01-30 10:42 +0000
---

## Table of Contents

-   [Statically-typed functional programming, Elm, Conway's Game of Life, and Emergence](#statically-typed-functional-programming-elm-conways-game-of-life-and-emergence)
    -   [Table of Contents](#table-of-contents)
    -   [Introduction](#introduction)
    -   [Definitions](#definitions)
    -   [Elm syntax](#elm-syntax)
        -   [Basic types](#basic-types)
        -   [Type aliases](#type-aliases)
        -   [Type variables](#type-variables)
        -   [Custom types](#custom-types)
        -   [Functions](#functions)
        -   [Conditionals](#conditionals)
        -   [Tuples](#tuples)
        -   [Records](#records)
        -   [Lists](#lists)
    -   [Statically-typed functional programming fundamentals](#statically-typed-functional-programming-fundamentals)
        -   [Mathematical functions](#mathematical-functions)
        -   [Types](#types)
        -   [Pure functions](#pure-functions)
        -   [Determinism](#determinism)
        -   [Referential transparency](#referential-transparency)
        -   [Side effects](#side-effects)
        -   [Immutability](#immutability)
        -   [Monads](#monads)
            -   [Maybe](#maybe)
            -   [Result](#result)
        -   [Higher-order functions](#higher-order-functions)
        -   [Anonymous functions](#anonymous-functions)
        -   [Partially-applied functions](#partially-applied-functions)
    -   [The Elm Architecture](#the-elm-architecture)
        -   [Subscriptions and commands](#subscriptions-and-commands)
    -   [Conway's Game of Life](#conways-game-of-life)
        -   [Rules](#rules)
        -   [Implementation](#implementation)
            -   [Modeling the universe](#modeling-the-universe)
            -   [Initializing the universe](#initializing-the-universe)
            -   [Updating the universe](#updating-the-universe)
            -   [Rendering the universe](#rendering-the-universe)
            -   [Putting it all together](#putting-it-all-together)
    -   [Determinism in the Game of Life](#determinism-in-the-game-of-life)
    -   [Emergence](#emergence)
    -   [Conclusion](#conclusion)
    -   [References](#references)
    -   [Acknowledgements](#acknowledgements)
    -   [About the author](#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](#conways-game-of-life). The [table of contents](#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:

```elm
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:

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

[Ellie](https://ellie-app.com/kvMYJTMLxjNa1)

### Type aliases

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

```elm
type alias Name = String
type alias Age = Int

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

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

[Ellie](https://ellie-app.com/kvN6qCkq9f8a1)

### Type variables

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

```elm
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:

```elm
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](https://ellie-app.com/kvN2KrBjhBSa1)

### 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:

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

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

[Ellie](https://ellie-app.com/kvN3kHLXG8ga1)

### Conditionals

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

```elm
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](https://ellie-app.com/kvMZqbrDSGga1)

### 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:

```elm
type alias Tamagotchi =
    ( String, Int )


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

      else
        hunger
    )
```

[Ellie](https://ellie-app.com/kyBpJcmfmf2a1)

### 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:

```elm
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:

```elm
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:

```elm
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:

```elm
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](https://ellie-app.com/kyPkMnjb8Jwa1)

To learn more about the Elm syntax, see the [official Elm syntax reference](https://elm-lang.org/docs/syntax).

## 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:

```elm
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](https://ellie-app.com/kvN6JVmvg2Sa1)

### 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.

or

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

or

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:

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

The following expression:

```elm
square 3 + 1 == 10
```

can be replaced with

```elm
(3 ^ 2) + 1 == 10
```

or equivalently

```elm
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:

```elm
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:

```elm
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](https://ellie-app.com/kvN4g4BR37Ba1)

### 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:

```elm
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:

```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:

```elm
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:

```elm
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](https://ellie-app.com/kwLZhVMKCfTa1)

#### 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:

```elm
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:

```elm
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:

```elm
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](https://ellie-app.com/kvN5PygWLGza1)

### 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]`:

```elm
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]`:

```elm
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](https://ellie-app.com/kvN3RmcBD85a1)

### 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:

```elm
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:

```elm
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:

```elm
doubleList [1, 2, 3]
```

[Ellie](https://ellie-app.com/kvN5ymtWphBa1)

## 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](https://guide.elm-lang.org/architecture/) 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](https://guide.elm-lang.org/effects/) 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.

```elm
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](https://ellie-app.com/kvMZZxmFjHWa1)

## Conway's Game of Life

### Rules

According to [Wikipedia](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life), 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:

```elm
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:

```elm
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:

```elm
type Cell
    = Live
    | Dead
```

#### Initializing the universe

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

```elm
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](https://package.elm-lang.org/packages/elm/browser/latest).

#### 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:

```elm
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:

```elm
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:

```elm
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:

```elm
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:

```elm
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](https://ellie-app.com/m3VxJwFh47xa1)

## 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

-   https://guide.elm-lang.org/
-   https://package.elm-lang.org/packages/elm/core/latest/
-   https://package.elm-lang.org/packages/elm/browser/latest/
-   https://package.elm-lang.org/packages/elm/html/latest
-   https://package.elm-lang.org/packages/elm/time/latest
-   https://www.manning.com/books/elm-in-action
-   https://rosettacode.org/wiki/Rosetta_Code
-   https://en.wikibooks.org/wiki/Haskell
-   https://wiki.haskell.org/All_About_Monads
-   https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
-   https://en.wikipedia.org/wiki/Boids

## Acknowledgements

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

Thanks to Richard for his excellent [_Elm in Action_](https://www.manning.com/books/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](https://twitter.com/charbelrami).