Statically-typed functional programming, Elm, Conway's Game of Life, and Emergence
Charbel Rami
Posted on January 30, 2023
Table of Contents
- Statically-typed functional programming, Elm, Conway's Game of Life, and Emergence
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" ]
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 }
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.
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 ++ "!"
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."
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
)
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
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.
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:
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.
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.
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.
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.
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]
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)
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"
)
]
[]
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 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.
Posted on January 30, 2023
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
January 30, 2023