functional-programming-snake/course/05-folding-time.md

Module 5 — Folding time

Time: ~2–3 h · You'll edit: JS js/src/game.js · Scala scala/src/Game.scala · F# fsharp/src/Game.fs Tests: JS cd js && node --test "test/m05-*.test.js" · Scala cd scala && ./test.sh M05 · F# cd fsharp && ./test.sh M05 Prerequisites: Modules 1–4

Why this module

Every interactive program you have seen has a loop at its heart:

while (true) {
  handleInput()     // reads the keyboard, changes some fields
  update()          // changes more fields
  render()          // reads the fields, draws
  sleep(150)
}

Two things are invisible in that loop: time and input. They are not values anywhere. They happen to the program, and the program's state is whatever is left behind in its variables after they have happened. That is why such programs are hard to test (you have to simulate time passing), hard to debug (by the time you see the bug, the state that caused it has been overwritten) and impossible to replay.

You already have everything you need to do better. In Module 2 you made everything that can happen into data: Action. In Modules 3 and 4 you wrote pure functions that compute the next state. In this module you put the two together into one function, update(state, action), and discover that a game is a fold over its actions. That one sentence gives you replays, a full history, and trivial tests, for free.

Learning objectives

After this module you can:

• implement update : (State, Action) → State by pattern matching on the action;
• explain why a whole game is fold(update, start, actions) and what that buys (replay, history, determinism);
• implement replay with a fold and history with a scan, and state the relationship between them;
• predict the final state of a short game from its start state and action list;
• describe how time will become "another action" in the rest of the course.

Concepts

One function for everything that happens

So far you have separate functions: tick(state) for time passing, turn(state, dir) for a key press. A program that uses them must know which one to call. Let us make that decision itself a pure function:

update : (GameState, Action) -> GameState

update looks at the action and dispatches: a Tick means "run a game step" (tick), a Turn(dir) means "ask to turn" (turn). In this module every other action (TogglePause, Restart, Frame) leaves the state unchanged; you will give them meaning in Module 10.

This is the most important function signature in the course. It has a name in several communities: Redux calls it a reducer, Elm calls it update, and in automata theory it is the transition function of a state machine. Everything the game can ever do is described by this one function and the start state.

From everyday programming: if you have written an event handler that does switch (event.type) with one case per kind of event, or a Redux reducer, you have written this dispatch. The difference here is that each case returns the next state instead of changing fields.

Dispatching on a sum type is pattern matching (Module 2). In Scala, case Action.Turn(dir) => ... extracts the direction; in F#, | Turn dir -> ...; in JS, switch (action.tag) and then read action.dir. For now a final catch-all case (case _, | _ ->, default:) handles the actions that do nothing. In Module 10 you will replace it by explicit cases, so that the Scala and F# compilers warn you if you ever forget one.

A game is a fold

Suppose you have a start state s0 and the list of everything that happened, in order: [a1, a2, a3]. The final state is

update(update(update(s0, a1), a2), a3)

You have seen that shape before. It is exactly what a left fold computes:

foldLeft over [a1, a2, a3] starting from s0 with update

  s0 --a1--> s1 --a2--> s2 --a3--> s3

update has precisely the type a fold wants for its step function: (accumulator, element) → accumulator. The accumulator is the game state, and the elements are the actions. Here is the same idea on a different example, a bank account folding over transactions:

JavaScript

const apply = (balance, tx) => (tx.tag === 'Deposit' ? balance + tx.amount : balance - tx.amount)
const txs = [{ tag: 'Deposit', amount: 50 }, { tag: 'Withdraw', amount: 20 }, { tag: 'Deposit', amount: 5 }]
txs.reduce(apply, 100)                 // 135

Scala

enum Tx:
  case Deposit(amount: Int)
  case Withdraw(amount: Int)
def apply(balance: Int, tx: Tx): Int = tx match
  case Tx.Deposit(a)  => balance + a
  case Tx.Withdraw(a) => balance - a
val txs = List(Tx.Deposit(50), Tx.Withdraw(20), Tx.Deposit(5))
txs.foldLeft(100)(apply)               // 135

F#

type Tx =
    | Deposit of int
    | Withdraw of int
let apply balance tx =
    match tx with
    | Deposit a -> balance + a
    | Withdraw a -> balance - a
let txs = [ Deposit 50; Withdraw 20; Deposit 5 ]
List.fold apply 100 txs                // 135

Note the argument orders, which trip people up: JS reduce(step, initial) is called on the array; Scala foldLeft(initial)(step) is too, with the initial value first; F# List.fold step initial list takes the list last (data last, again). In all three, the step function takes the accumulator first and the element second, which is why update takes the state first.

A game of Snake is, literally, actions.reduce(update, start). Time and input have become a list.

From everyday programming: databases rely on the same idea. A database writes every change to a log (the write-ahead log) before it applies it; after a crash, it rebuilds its state by replaying the log over the last saved snapshot. A bank works the same way: your balance is a fold over your transactions, which is why your statement lists the transactions and not only the balance.

History is a scan

A fold gives you only the final state. Sometimes you want every state along the way: to draw a replay frame by frame, to step backwards through a game in a debugger, or to find the first state where something went wrong. The operation that keeps every intermediate accumulator is called a scan:

scanLeft over [a1, a2, a3] starting from s0 with update   =   [s0, s1, s2, s3]

Notice two facts, which the tests check: the result has one more element than there are actions (it includes the start), and its last element is the fold's result. On the bank account:

JavaScript

// JS arrays have no scan. You will build one for game states in Exercise 5.3.
// The expected result for the bank example would be: [100, 150, 130, 135]

Scala

txs.scanLeft(100)(apply)               // List(100, 150, 130, 135)

F#

List.scan apply 100 txs                // [100; 150; 130; 135]

scanLeft is in the standard library of Scala, and List.scan in F#'s. In JavaScript you can build a scan out of reduce, by making the accumulator the list of states so far instead of the latest state. Think about what the step function then has to do. (Building a new array on every step with [...acc, next] costs O(n) per step and O(n²) overall. For games of a few thousand steps that does not matter; persistent lists, as in Scala and F#, avoid it.)

What the fold gives you for free

Because a game is fold(update, start, actions) and update is pure:

• Replays. To store a whole game you do not need a video. You need the start state, which is fully determined by the seed (newGame(seed)), and the list of actions. Replaying them through update reproduces every state exactly, apples included, because the random seed is in the state (Module 4).

• Deterministic tests. A test is "this start, these actions, this expected end". No timers, no mocks, no sleeping. The fixture twelve-actions-eat-one-apple is a whole little game in one test case:

  start: the standard 20x20 snake (10,10) (9,10) (8,10), heading Right, apple at (1,9)
  actions: Turn Up, Tick, Turn Left, then 9 x Tick
  

  Work it out: after Turn Up and one Tick, the head is at (10,9). After Turn Left, nine ticks move it along row 9 from x = 10 to x = 1, where the apple is. On the last tick the snake eats: it grows to four segments (1,9) (2,9) (3,9) (4,9), the score becomes 1, and a new apple is drawn from the seed and lands at (6,5). Every number in the expected state follows from the start state and the list.

• Bug reports you can reproduce. If players' games were logged as seed plus actions, any crash could be replayed exactly on a developer's machine.

• Splitting and resuming. Since a fold over a concatenated list is a fold over the first part followed by a fold over the second, replay(s, a ++ b) == replay(replay(s, a), b). You can save a game anywhere (only the state) and continue later.

Notice what made this possible: no step of the game reads anything except its arguments. A single Math.random() or Date.now() hidden in advance would break every bullet point above.

Time is only another action

Look at the actions again: Tick is not "time". It is a value that says "one step of time has passed". The game does not know about milliseconds, timers, or clocks. Something outside the game decides when to put a Tick into the list.

That is the plan for the rest of the course:

                 clock --every 150 ms--> Tick  \
                                                 merge --> actions --> scan(update, newGame(seed)) --> states
   keyboard --ArrowUp, w, ...-----> Turn(dir)  /

In Module 8 you will build streams: values that describe "a Tick every 150 ms" and "a Turn for every arrow key", that can be merged into one stream of actions, and then scanned with update, exactly the scan you write today, except that the list of actions arrives over time and never ends. In Module 9 the runtime feeds real clock ticks and key presses in. In Module 10 you will even make the snake speed up without touching the clock: a faster Frame action plus a counter in the state (that is what the frame field is for).

The game loop from the top of this module becomes: the states of the game are a scan of update over the stream of actions. Nothing in the game itself will need to change.

Exercises

About test names. The test titles quoted under "Tests" are the JavaScript ones; the JS runner prints them with the module in front (m05 history has one more state than there are actions). The Scala and F# suites use the same titles. Failing tests are reported by name when you run the module's tests; to read all titles, open scala/test/M05Game.test.scala or fsharp/tests/M05Game.fs. Fixture-based tests have the same case names in every track (JS m05 replay: twelve-actions-eat-one-apple, Scala/F# replay: twelve-actions-eat-one-apple).

Exercise 5.1 — update

Tick runs a game step (tick from spawn), Turn(dir) asks to turn (turn from rules), every other action returns the state unchanged.

JavaScript

export const update = (state, action) => ...

Scala

def update(state: GameState, action: Action): GameState

F#

let update (state: GameState) (action: Action) : GameState

Fixture: fixtures/m05-update.json: tick-moves-the-snake, tick-eating-respawns-apple, tick-into-wall-is-game-over, tick-while-paused-does-nothing, turn-sets-next-dir, turn-against-direction-is-ignored, turn-while-paused-is-ignored.

Watch out: do not re-implement any rule here. update only dispatches; all the behaviour is already in tick and turn. Notice that several fixture cases (paused, against direction) pass "for free" because the rules you wrote are total.

Exercise 5.2 — replay

Apply all actions in order, starting from state, and return the final state.

JavaScript

export const replay = (state, actions) => ...

Scala

def replay(state: GameState, actions: List[Action]): GameState

F#

let replay (state: GameState) (actions: Action list) : GameState

Fixture: fixtures/m05-replay.json: twelve-actions-eat-one-apple, no-actions-returns-the-start.

Exercise 5.3 — history

Like replay, but return every state: [state, afterFirst, afterSecond, ...]. Its length is actions.length + 1.

JavaScript

export const history = (state, actions) => ...

Scala

def history(state: GameState, actions: List[Action]): List[GameState]

F#

let history (state: GameState) (actions: Action list) : GameState list

Fixture: fixtures/m05-history.json: no-actions-gives-just-the-start, every-intermediate-state-is-kept. Tests: history has one more state than there are actions, history starts at the start state and ends where replay ends.

Watch out (JS): no .push(. Each step must produce a new array. The previous state is the last element of the accumulator; acc.at(-1) reads it.

Run

• JS: cd js && node --test "test/m05-*.test.js"
• Scala: cd scala && ./test.sh M05
• F#: cd fsharp && ./test.sh M05

Then run your track's whole suite (./test.sh): Modules 1–5 and the purity audit should all be green. You now have a complete, pure, deterministic Snake game. It cannot be seen or played yet; that is Modules 6 to 9.

Hints

Exercise 5.1 (update) — nudge

Three branches: Tick, Turn, everything else. Which function handles each?

Exercise 5.1 (update) — stronger hint

JS: switch (action.tag) with case 'Tick', case 'Turn' (read action.dir) and default. Import tick from ./spawn.js and turn from ./rules.js. Scala: action match with case Action.Tick, case Action.Turn(dir), case _, calling Spawn.tick and Rules.turn. F#: match action with | Tick -> ... | Turn dir -> ... | _ -> ..., calling Spawn.tick and Rules.turn.

Exercise 5.1 (update) — near-solution (try the others first)

export const update = (state, action) => {
  switch (action.tag) {
    case 'Tick': return ___
    case 'Turn': return ___
    default: return ___
  }
}

def update(state: GameState, action: Action): GameState = action match
  case Action.Tick      => ___
  case Action.Turn(dir) => ___
  case _                => ___

let update (state: GameState) (action: Action) : GameState =
    match action with
    | Tick -> ___
    | Turn dir -> ___
    | _ -> ___

Exercise 5.2 (replay) — nudge

Re-read "A game is a fold". The bank account example is the same shape.

Exercise 5.2 (replay) — stronger hint

The step function is update, the initial value is state, the list is actions. JS reduce, Scala foldLeft, F# List.fold. Mind each language's argument order.

Exercise 5.2 (replay) — near-solution (try the others first)

export const replay = (state, actions) => actions.reduce(___, ___)

def replay(state: GameState, actions: List[Action]): GameState = actions.foldLeft(___)(___)

let replay (state: GameState) (actions: Action list) : GameState = List.fold ___ ___ ___

Exercise 5.3 (history) — nudge

Scala and F#: the standard library already has the operation; see "History is a scan". JS: fold, but with a list of states as the accumulator.

Exercise 5.3 (history) — stronger hint

Scala scanLeft, F# List.scan. In JS, start the reduce with [state]. At each action, compute the next state from the last state in the accumulator, and return a new array with that next state appended.

Exercise 5.3 (history) — near-solution (try the others first)

export const history = (state, actions) =>
  actions.reduce((states, action) => [...states, update(___, action)], ___)

def history(state: GameState, actions: List[Action]): List[GameState] = actions.scanLeft(___)(___)

let history (state: GameState) (actions: Action list) : GameState list = List.scan ___ ___ ___

Check your understanding

1. Write down the type of the step function that reduce/foldLeft/List.fold expects. Why does that force update to take the state as its first argument?
2. Predict: replay(s, []), and history(s, []). Now history(s, [Tick]).length.
3. Show, using the definition of a fold, that replay(s, a.concat(b)) equals replay(replay(s, a), b). What practical feature does this law give you?
4. To store a replay of a 10-minute game, what exactly do you need to save? Why is a single number enough to reproduce every apple?
5. Suppose someone "optimises" spawnApple by using Math.random() when the board is large. Which of the "free" benefits in this module break, and how would you notice in the tests?
6. update currently ignores TogglePause. Sketch (in words) what it should do in Module 10. Will replay or history need to change? Why not?
7. Who decides when a Tick happens? Is that decision part of the game? Where in the big-picture diagram of Module 0 will it live?
8. A teammate suggests making update also draw the new state, "since it's called every frame anyway". What would you lose? (Think about history of a 1000-action game.)

In production

• Redux is built on exactly this idea: the application state is actions.reduce(reducer, initialState), conceptually. The Redux DevTools use it for time-travel debugging: they keep the action log and let you jump to any past state.
• Elm applications are a fold of update over messages; the Elm debugger lets you export a session and replay it on another machine, see "The Perfect Bug Report".
• Event sourcing stores a system's history as a log of events and computes the current state by folding over it; see Martin Fowler's Event Sourcing. Banks, ledgers and many large systems work this way.
• Deterministic lockstep networking in strategy games sends only the players' actions over the network; every machine folds the same actions over the same start state. See Glenn Fiedler's Deterministic Lockstep.
• Elmish brings the same model-update architecture to F# (elmish.github.io), and fs2 in Scala has scan on streams, which is what you will build by hand in Module 8 (fs2.io).

Further reading

• Graham Hutton, "A tutorial on the universality and expressiveness of fold" — why so many functions are folds, and how to prove things about them (like the replay law above).
• Fold (higher-order function) (Wikipedia) — left and right folds, and their relation to scans.
• Array.prototype.reduce (MDN) — JavaScript's fold, including the empty-array pitfall.
• F# List module and Scala List API — fold/scan and foldLeft/scanLeft.
• The Elm Architecture — model, update, view: the structure this course is building, from Elm's own guide.
• Mealy machine (Wikipedia) — a state machine whose step produces outputs from the current state and input; a preview of how Module 8 will model streams.
• Conal Elliott and Paul Hudak, "Functional Reactive Animation" — the paper that started treating time-varying values and events as first-class values, the idea behind Modules 8 and 9.