functional-programming-snake/course/02-the-game-as-data.md

Module 2 — The game as data

Time: ~3 h · You'll edit: JS js/src/model.js · Scala scala/src/Model.scala · F# fsharp/src/Model.fs Tests: JS cd js && node --test "test/m02-*.test.js" · Scala cd scala && ./test.sh M02 · F# cd fsharp && ./test.sh M02 Prerequisites: Module 1

Why this module

In the usual object-oriented Snake, the game is spread over objects that each hold a bit of state and change it: a Snake with a body array and a direction field, an Apple with a pos, a Game with score, isPaused, isOver, a timer handle, and a random generator hidden somewhere. To save or replay a game, you would have to find all of those pieces and copy them at the right moment.

We are going to do the opposite: the whole game is one value. One immutable record that contains everything needed to draw the current frame and compute the next one. If you have that value, you have the game. You can print it, compare it with ==, store it in a test fixture, or keep a list of them as a history.

Choosing that record is the most important design decision of the course. Every later module reads it, and the shared test fixtures are written in its shape. So before you are shown the course's model, you will design your own.

Learning objectives

After this module you can:

• design a minimal immutable state for a game and justify each field;
• explain algebraic data types (product types and sum types) and how each language spells them;
• apply "make illegal states unrepresentable" to choose between representations;
• implement the model's small functions (delta, opposite, initialState, and in JS point, pointEquals, Action);
• compare your design with the canonical one and name the trade-offs.

Concepts

Design it yourself first

Take a sheet of paper and fifteen minutes. Do not read past the "Stop here" line until you have written something down, and do not open this module's stub file yet (js/src/model.js, scala/src/Model.scala, fsharp/src/Model.fs): its type declarations already contain the course's answer. You will open it for the exercises, after the reveal. It does not matter if your answer differs from the course's; what matters is that you have thought about the questions, so that the canonical model answers questions you have actually asked.

Your task: write down the type of "the state of a game of Snake", in the language of your track or in pseudo-code. Use these questions to guide you:

1. What is the minimum information you need to (a) draw the current screen and (b) compute the next state when time passes or a key is pressed? Is there anything you were tempted to include that can be computed from the rest? (Candidates: the snake's length, the set of occupied cells, pixel coordinates.)
2. How do you represent the snake's body? A list of cells? In which order? Moving the snake means "add a new cell at the front, remove the last". Which end of a list is cheap to add to? (Scala's List and F#'s list are singly linked lists, like the ones from a data structures course: each cell holds one element and a pointer to the rest.)
3. How many directions do you need to store? Imagine the player presses two keys very quickly, both before the snake moves again. What do you need to remember to handle that well? (Hint: there is "the way the snake is going" and "the way the player has asked it to go".)
4. Is there always an apple? Think of the moment right after the snake eats it, and of a board completely filled by the snake. How do you represent "no apple"?
5. Where does randomness come from? The apple appears on a random free cell. If the generator's state lives outside the game state, is a function nextState(state) still pure? Could you replay a game?
6. How do you represent "playing", "paused", "game over" and "you won"? Would two booleans isPaused and isOver do? How many combinations do two booleans have, and how many of them make sense?
7. What about the size of the board? Hard-code it, or store it? Think about writing a test where the snake hits a wall: would you rather draw a 20 x 20 board or a 5 x 5 one?
8. What happens in the game that is not a change of time? List all the things that can happen (a tick of the clock, a key press, ...). Could those be data too?

---

Stop here. Write your design down before reading on.

---

The canonical model

Here is the model the course uses. (Now you may open your stub file: in Scala and F# these declarations are already written there for you, and in JS they are the JSDoc comments at the top of model.js.) All three tracks use the same fields with the same meaning, which is what lets one JSON fixture test all three.

JavaScript (JS has no types, so the shape is documented with JSDoc comments)

/** @typedef {{x: number, y: number}} Point */
/** @typedef {'Up'|'Down'|'Left'|'Right'} Direction */
/** @typedef {'Playing'|'Paused'|'GameOver'|'Won'} Status */
/** @typedef {{width: number, height: number, snake: Point[], dir: Direction, nextDir: Direction,
 *   apple: Point|null, seed: number, score: number, status: Status, frame: number}} GameState */
// Action: {tag:'Tick'} | {tag:'Turn', dir} | {tag:'TogglePause'} | {tag:'Restart'} | {tag:'Frame'}

Scala

final case class Point(x: Int, y: Int)
enum Direction:
  case Up, Down, Left, Right
enum Status:
  case Playing, Paused, GameOver, Won
enum Action:
  case Tick
  case Turn(dir: Direction)
  case TogglePause
  case Restart
  case Frame
final case class GameState(
    width: Int, height: Int,
    snake: List[Point],       // head first
    dir: Direction, nextDir: Direction,
    apple: Option[Point],
    seed: Long,               // unsigned 32-bit, 0 until 2^32
    score: Int, status: Status, frame: Int)

F#

type Point = { X: int; Y: int }
type Direction = Up | Down | Left | Right
type Status = Playing | Paused | GameOver | Won
type Action =
    | Tick
    | Turn of Direction
    | TogglePause
    | Restart
    | Frame
type GameState =
    { Width: int; Height: int
      Snake: Point list        // head first
      Dir: Direction; NextDir: Direction
      Apple: Point option
      Seed: uint32
      Score: int; Status: Status; Frame: int }

A fresh game is 20 x 20, the snake is (10,10), (9,10), (8,10) heading Right (both dir and nextDir), there is no apple yet, the seed is whatever you were given, the score is 0, the status Playing, and frame is 0. The y axis grows downward, as on a screen: Up is {x: 0, y: -1}.

Now compare with your design, question by question.

1. Minimal state. Everything in GameState is needed to compute the future. Nothing is stored that can be derived: the length is snake.length, the occupied cells are the snake's points, pixel positions are the view's business (Module 6). Storing derived data creates a second source of truth that can disagree with the first. (A trade-off you might make in a bigger game: cache a set of occupied cells for speed, and accept that you must keep it consistent.)

2. Head first. The snake is a list of points with the head at index 0. Every move adds a cell at the head and (usually) removes the tail. For Scala's List and F#'s list, adding at the front (h :: rest) is O(1) and shares the whole old list. Reading the head is O(1) too. In JS it hardly matters for speed, but the same order keeps the tracks identical.

3. Two directions. dir is the direction the snake last moved. nextDir is the direction it will move on the next step, the most recent valid key press. A key press only changes nextDir; a step of the game moves the head in nextDir and then records it as dir. Why both? You will discover in Module 3 that if you only keep one, a fast player can make the snake reverse into itself. Keep that question in mind.

4. Optional apple. There is not always an apple: at the very start (before the first one is placed), and when the snake has filled the whole board. JS uses null for "no apple"; Scala and F# use Option[Point] / Point option. An Option is a small sum type (see "Algebraic data types" below) with two cases: Some(p), which holds a point, and None, which holds nothing. You cannot use the point inside without first checking which case you have (usually with a match), so the compiler forces every reader to handle the "none" case. The board-full situation becomes the status Won in Module 4.

From everyday programming: null is the usual way to say "nothing here", and the NullPointerException (or TypeError: Cannot read properties of null) is the usual price: nothing reminds the reader that the value might be missing. Java's Optional<Point>, C#'s nullable types and TypeScript's Point | null with strict null checks are all attempts to make "might be missing" visible in the type, which is what Option does.

5. The seed is in the state. The apple's position comes from a pseudo-random generator, and a generator is a little machine with an internal state (a 32-bit number, the seed). If that state lived in a global variable, every function that places an apple would read and change a global, so it would not be pure, and two runs could differ. By putting the seed inside the game state, "place an apple" becomes a pure function state → state that takes the seed out, uses it, and stores the new seed. Same starting seed, same game, every time. Module 4 is all about this.

6. Status as one value. Two booleans have four combinations; "paused and game over" is meaningless, and every function would need to decide what to do with it. A Status with four named cases has exactly the four states that make sense. This idea has a name; see "Making illegal states unrepresentable" below.

7. Board size in the state. Storing width and height costs two fields and pays back enormously in testing: the fixtures use boards of 5 x 5 and 3 x 2, small enough to draw by hand. A function that reads a global WIDTH constant could not be tested on a tiny board.

8. Events as data. Everything that can happen to the game is a value of type Action: Tick (time passes one step), Turn(dir) (the player asks to turn), TogglePause, Restart, and Frame (a finer-grained clock you will use in Module 10 for speed-ups). Module 5 shows why this is powerful: a whole game becomes "a start state plus a list of actions".

There is one more field, frame. It counts small clock frames so that the snake can speed up later without changing the clock (Module 10). Until then it stays 0.

Did your design differ? Common alternatives and their costs:

Alternative	What goes wrong
A 2D grid of cells ('empty' | 'snake' | 'apple')	Does not record the snake's order (which cell is the head? where is the tail?). Allows two apples, or snake cells that are not connected.
Direction stored as a vector {dx, dy}	{dx: 2, dy: 3} is representable but means nothing. You also lose the names in pattern matches.
isPaused, isOver, hasWon booleans	Eight combinations, four meaningful.
Score derived from the length	Works until a feature changes length without scoring (or the reverse). A judgement call; we store it.
The random generator as an object in the state	Objects with hidden mutable state are exactly what we are removing. A number is a value.

Algebraic data types

The model is built from two kinds of types. Together they are called algebraic data types (ADTs).

A product type holds several values at the same time: a Point has an x and a y. Its number of possible values is the product of its fields' (hence the name). Records, case classes, tuples and plain JS objects are product types.

A sum type is one of several alternatives: a Direction is Up or Down or Left or Right. An Action is Tick or Turn (carrying a direction) or ... The number of possible values is the sum of the alternatives'. Each alternative is called a case (or variant, or constructor).

From everyday programming: a class with fields is a product type. A plain Java or C# enum is a sum type whose cases carry no data. In object-oriented code, a sum type whose cases carry different data is usually an abstract base class with one subclass per case (Shape with subclasses Circle and Square), plus instanceof checks or the visitor pattern to tell them apart. A sum type says the same thing more directly: here is the complete list of cases, and nothing else can be a Shape.

Each track spells them differently. In Scala, a product is a case class (an immutable record) and a sum is an enum (or a sealed trait with case classes). F# spells products as records and sums as discriminated unions (DU): type Shape = Circle of float | Square of float. JavaScript has no sum types, so we encode them by convention, as tagged unions.

Here is the same small sum type, unrelated to the game, in all three languages: a traffic light, and a function that gives the next light.

JavaScript

// A nullary sum type: plain strings are enough.
/** @typedef {'Red'|'Green'|'Yellow'} Light */
const nextLight = (l) => ({ Red: 'Green', Green: 'Yellow', Yellow: 'Red' })[l]

// A sum type whose cases carry data: objects with a `tag` field.
/** @typedef {{tag: 'Circle', r: number} | {tag: 'Square', side: number}} Shape */
const area = (s) => {
  switch (s.tag) {
    case 'Circle': return Math.PI * s.r * s.r
    case 'Square': return s.side * s.side
  }
}

Scala

enum Light:
  case Red, Green, Yellow
def nextLight(l: Light): Light = l match
  case Light.Red    => Light.Green
  case Light.Green  => Light.Yellow
  case Light.Yellow => Light.Red

enum Shape:
  case Circle(r: Double)
  case Square(side: Double)
def area(s: Shape): Double = s match
  case Shape.Circle(r)    => math.Pi * r * r
  case Shape.Square(side) => side * side

F#

type Light = Red | Green | Yellow
let nextLight l =
    match l with
    | Red -> Green
    | Green -> Yellow
    | Yellow -> Red

type Shape =
    | Circle of r: float
    | Square of side: float
let area s =
    match s with
    | Circle r -> System.Math.PI * r * r
    | Square side -> side * side

The match in Scala and F# is called pattern matching: it takes a sum apart. It looks like a switch statement, with two differences. First, each case can take the value apart: Circle(r) both checks that s is a circle and gives its radius the name r. Second, the whole match is an expression that returns a value, so no return or break is needed. Patterns work on lists too: in F#, [] matches the empty list and x :: rest matches a list whose first element is x, followed by the list rest. (In Scala the same patterns are written Nil and x :: rest.) In JavaScript, a switch on the tag field plays the role of match, and you read the data out of the object yourself.

Note the JS lookup-table trick in nextLight: an object literal used as a function from a fixed set of strings to values. It is often the clearest way to write a function over a nullary sum type.

The important difference between the languages is exhaustiveness checking. If you add case Triangle to Scala's Shape and forget to handle it in area, the compiler warns you. F# does the same. JavaScript will silently return undefined. In JS you must be your own exhaustiveness checker; the fixtures, which cover every case, help.

Making illegal states unrepresentable

Yaron Minsky's advice from Effective ML is: make illegal states unrepresentable. Choose types so that a value that makes no sense cannot be built at all. Then no function ever has to check for it, and no bug can produce it.

You have already seen it at work: Status instead of booleans, Direction instead of a vector, Option[Point] instead of "a point plus a flag hasApple". Each choice removes nonsense values from the type.

Be honest about what our model still allows. A GameState can still be built with:

• an empty snake, or a snake whose segments are not next to each other;
• an apple on top of the snake;
• dir and nextDir pointing in opposite directions;
• in Scala, a seed that is negative or ≥ 2^32 (a Long is wider than 32 bits).

Types could rule out some of these (a NonEmptyList for the snake, an opaque Seed type), at the price of more ceremony. This course keeps the model simple and maintains the rest as invariants: properties that every function promises to preserve. initialState creates a valid state, and every rule in Module 3 turns a valid state into a valid state. Choosing how much to push into types is a real engineering trade-off, and you should be able to argue both sides.

Equality: identity or structure?

When are two points equal? In Scala, case classes compare structurally: Point(1, 2) == Point(1, 2) is true. F# records do the same. In JavaScript, === on objects compares identity:

const a = { x: 1, y: 2 }
a === { x: 1, y: 2 }     // false: two different objects
a === a                  // true

That is why the JS track needs a pointEquals(a, b) function, and why Module 1's contains takes an eq argument. Scala and F# need neither (the Scala test for pointEquals checks == on the same four fixture cases).

Smart constructors

A smart constructor is a function that builds a value, possibly checking or normalising it, instead of building it directly. point(x, y) in JS is the simplest possible one: it builds {x, y}, so every point in the program has exactly that shape (no extra fields, no typos like {X: 1}). initialState(seed) is another: it is the only place that knows what a fresh game looks like. In a stricter design, a smart constructor would also reject invalid input, for example makeSeed(n) returning None for negative numbers.

Actions in JavaScript

In Scala and F#, Action is a type with five cases, already declared for you. In JavaScript you build the values yourself, in model.js:

export const Action = {
  Tick: ...,            // the value { tag: 'Tick' }
  Turn: (dir) => ...,   // a function: Action.Turn('Left') is { tag: 'Turn', dir: 'Left' }
  TogglePause: ...,
  Restart: ...,
  Frame: ...,
}

Cases with no data are constants; a case with data (Turn) is a function that builds a tagged object. (The stub uses getters only so that the file loads before you have written it; replace them with plain values.)

Exercises

About test names. The test titles quoted under "Test"/"Tests" are the JavaScript ones; the JS runner prints them with the module in front (m02 opposite is its own inverse). The Scala and F# suites test the same things, but where JS checks a function you write (point, Action) they check the declarations you were given instead: Point holds its coordinates, Action.Turn carries the direction (F#: Action Turn carries the direction), the other Actions are distinct constants. Failing tests are reported by name when you run the module's tests; to read all titles, open scala/test/M02Model.test.scala or fsharp/tests/M02Model.fs. Fixture-based tests have the same case names in every track (JS m02 delta: up, Scala/F# delta: up; the pointEquals cases are labelled pointEquals (case-class ==) in Scala and pointEquals (record =) in F#).

Exercise 2.0 — Your own design (paper)

Complete the design questions at the top of "Concepts" before reading the canonical model. Afterwards, write three sentences: one thing your design did better or differently, one thing the canonical model does that you had not thought of, and one trade-off you would make differently in a bigger game. Keep the sheet; Module 11 asks you to do this again for Pong.

Exercise 2.1 — point and pointEquals (JS)

JavaScript

export const point = (x, y) => ...        // point(3, 4) -> { x: 3, y: 4 }
export const pointEquals = (a, b) => ...  // true iff same x and same y

Scala — nothing to write: Point(3, 4) and == already do this. Check in the REPL that Point(1, 2) == Point(2, 1) is false. F# — nothing to write: { X = 3; Y = 4 } and = already do this.

Fixture: fixtures/m02-point-equals.json (cases same-point, different-x, different-y, swapped-coordinates). Test: point builds a {x, y} record.

Exercise 2.2 — delta

The unit step for each direction: Up (0,-1), Down (0,1), Left (-1,0), Right (1,0).

JavaScript

export const delta = (dir) => ...         // delta('Up') -> { x: 0, y: -1 }

Scala

def delta(dir: Direction): Point

F#

let delta (dir: Direction) : Point

Fixture: fixtures/m02-delta.json (cases up, down, left, right). Watch out: y grows downward, so Up is negative.

Exercise 2.3 — opposite

JavaScript

export const opposite = (dir) => ...      // opposite('Left') -> 'Right'

Scala

def opposite(dir: Direction): Direction

F#

let opposite (dir: Direction) : Direction

Fixture: fixtures/m02-opposite.json. Test: opposite is its own inverse (for every d, opposite(opposite(d)) == d). You will use opposite in Module 3 to reject 180-degree turns.

Exercise 2.4 — Action (JS)

Fill in the Action object as described in "Actions in JavaScript" above. Scala and F#: nothing to write; read the Action declaration and make sure you can build Turn(Left) and match on it.

Tests: Action constants are tagged records, Action.Turn carries the direction.

Exercise 2.5 — initialState

JavaScript

export const initialState = (seed) => ...

Scala

def initialState(seed: Long): GameState

F#

let initialState (seed: uint32) : GameState

A 20 x 20 board; snake (10,10), (9,10), (8,10); dir and nextDir both Right; no apple; the given seed, stored as given; score 0; status Playing; frame 0.

Fixture: fixtures/m02-initial-state.json (cases seed-7 and seed-is-stored-as-given, which uses the largest 32-bit seed, 4294967295). Watch out: the order of the snake's points matters (head first), and in JS use your point function so that every point has the same shape.

Run

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

Hints

Exercise 2.1 (pointEquals) — nudge

Two points are equal when both coordinates are equal. Numbers compare by value with ===, so compare the fields, not the objects.

Exercise 2.1 (pointEquals) — stronger hint

pointEquals is a boolean expression with one &&. point is an arrow function returning an object literal; remember that (x, y) => { x, y } is parsed as a function body, not an object. Wrap the object in parentheses.

Exercise 2.1 (pointEquals) — near-solution (try the others first)

export const point = (x, y) => ({ ___ })
export const pointEquals = (a, b) => a.x === ___ && ___

Exercises 2.2 and 2.3 (delta, opposite) — nudge

Both are functions from a four-case sum type to something. Look at the traffic-light example again.

Exercises 2.2 and 2.3 (delta, opposite) — stronger hint

JS: an object literal indexed by the direction string ({ Up: ..., Down: ..., ... }[dir]), or a switch. Scala and F#: a match with one line per case. In Scala the cases are Direction.Up etc. (or import Direction.* to write Up). You can build delta's result with point(...) (JS), Point(...) (Scala) or a record expression { X = ...; Y = ... } (F#).

Exercises 2.2 and 2.3 (delta, opposite) — near-solution (try the others first)

export const opposite = (dir) => ({ Up: ___, Down: ___, Left: ___, Right: ___ })[dir]

def opposite(dir: Direction): Direction = dir match
  case Direction.Up    => ___
  case Direction.Down  => ___
  case Direction.Left  => ___
  case Direction.Right => ___

let opposite (dir: Direction) : Direction =
    match dir with
    | Up -> ___
    | Down -> ___
    | Left -> ___
    | Right -> ___

delta has the same shape, returning points.

Exercise 2.4 (Action) — nudge

Each constant is an object with a single tag field. Turn is the only one with data.

Exercise 2.4 (Action) — stronger hint

Replace get Tick() { return todo('m02') } by Tick: { tag: 'Tick' }, and so on. Turn is an arrow function returning { tag: 'Turn', dir } (wrapped in parentheses).

Exercise 2.4 (Action) — near-solution (try the others first)

export const Action = {
  Tick: { tag: ___ },
  Turn: (dir) => ({ tag: ___, ___ }),
  TogglePause: ___,
  Restart: ___,
  Frame: ___,
}

Exercise 2.5 (initialState) — nudge

This is a single record literal. Read the fixture m02-initial-state.json: the expected value is exactly the record you must build (with the seed from args).

Exercise 2.5 (initialState) — stronger hint

Ten fields: width, height, snake, dir, nextDir, apple, seed, score, status, frame. In Scala/F#, "no apple" is None; in JS it is null. In Scala the enum values are Direction.Right and Status.Playing.

Exercise 2.5 (initialState) — near-solution (try the others first)

export const initialState = (seed) => ({
  width: 20, height: 20,
  snake: [point(10, 10), ___, ___],
  dir: ___, nextDir: ___,
  apple: ___, seed, score: ___, status: ___, frame: ___,
})

def initialState(seed: Long): GameState =
  GameState(20, 20, List(Point(10, 10), ___, ___), Direction.Right, ___, ___, seed, ___, ___, ___)

let initialState (seed: uint32) : GameState =
    { Width = 20; Height = 20
      Snake = [ { X = 10; Y = 10 }; ___; ___ ]
      Dir = Right; NextDir = ___
      Apple = ___; Seed = seed; Score = ___; Status = ___; Frame = ___ }

Check your understanding

1. Why is the snake stored head first? Name one operation that would be more expensive (in Scala or F#) if it were tail first.
2. Explain in your own words why seed is part of GameState. What would you lose if it were a global variable that the apple-placing function updates?
3. How many values does the type { isPaused: boolean, isOver: boolean } have? How many does Status have? Which illegal combinations disappear?
4. Name two illegal states that our GameState can still represent. For one of them, sketch a type that would rule it out, and say what it would cost.
5. In JS, what does [point(1, 2)].includes(point(1, 2)) return, and why? How does Scala's List(Point(1, 2)).contains(Point(1, 2)) differ?
6. Predict: if you add a sixth case Grow to Action in Scala and forget to handle it in a match, what happens at compile time? What happens in JS if you forget a case in a switch?
7. Why store width and height in the state rather than as global constants? Give a concrete testing scenario.
8. dir and nextDir: describe a sequence of key presses in which they differ. (Module 3 will ask what can go wrong if we only had one.)

In production

• Elm models every application as a single immutable Model record plus a Msg custom type for everything that can happen, exactly like GameState and Action. See custom types in the Elm guide.
• TypeScript checks JavaScript tagged unions at compile time: a switch on tag can be made exhaustive. See discriminated unions. (We use plain JS in this course, so you are the type checker.)
• Redux actions are tagged objects ({ type: 'todos/added', payload }), the same idea as our Action.
• Domain modelling with types is a whole discipline in the F# and Scala communities; see Scott Wlaschin's work below.

Further reading

• Yaron Minsky, "Effective ML Revisited" — the origin of "make illegal states unrepresentable", with a worked example of redesigning a type.
• Scott Wlaschin, "Designing with types: Making illegal states unrepresentable" — the same idea, step by step, in F#.
• Alexis King, "Parse, don't validate" — why smart constructors that return a more precise type beat checks scattered through the code.
• Algebraic data type (Wikipedia) and Tagged union (Wikipedia) — definitions, and how many languages encode them.
• Scala 3 reference: algebraic data types with enums — the enum syntax used in Model.scala.
• F# discriminated unions and F# records — official docs for the F# side.
• Tony Hoare, "Null References: The Billion Dollar Mistake" — why Option is better than null, from the man who invented null.