lucasw89/functional-programming-snake
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
functional-programming-snake/course/01-purity-and-immutability.md
T

34 KiB
Raw Permalink Blame History

Module 1 — Purity and immutability

Time: ~3 h · You'll edit: JS js/src/util.js · Scala scala/src/Util.scala · F# fsharp/src/Util.fs Tests: JS cd js && node --test "test/m01-*.test.js" · Scala cd scala && ./test.sh M01 · F# cd fsharp && ./test.sh M01 Prerequisites: Module 0

Why this module

Look at this piece of a typical Snake game:

function step() {
  const head = nextHead()
  snake.body.unshift(head)            // changes the array everyone shares
  if (samePlace(head, apple)) {
    score++                           // changes a global
    apple = randomFreeCell()          // a different answer every call
  } else {
    snake.body.pop()                  // changes it again
  }
}

step() takes no arguments and returns nothing. Everything it does is a change somewhere else. To know what it does you need to know the current value of snake, apple, score, what randomFreeCell() will return this time, and who else is holding a reference to snake.body. To test it you have to set up globals, call it, and inspect the globals afterwards. To replay a game you would have to record every random number.

The fix is not a library. It is two habits: write functions whose result depends only on their arguments, and never change data; build new data instead. This module makes those habits precise, shows how they look in JavaScript (which does not enforce them), Scala and F#, introduces the tools that replace loops (map, filter, reduce) and gives you a few small helpers you will use in every later module.

Learning objectives

After this module you can:

  • explain referential transparency and decide whether a given expression has it;
  • distinguish a constant binding (const, val, let) from immutable data, and shallow from deep freezing;
  • update records and arrays without mutation in all three languages (spread, copy, with);
  • replace a loop with map, filter and reduce (a fold), and pass functions as arguments;
  • implement small list helpers (range, dropLast, contains) without loops or reassignment;
  • compose functions (JS pipe/compose, Scala andThen/compose, F# |>/>>) and predict the order in which they apply.

Concepts

Referential transparency

An expression is referentially transparent if you can replace it with its value anywhere in the program without changing what the program does.

const add = (a, b) => a + b
const x = add(2, 3) + add(2, 3)
// You may rewrite this as 5 + 5, or as const five = add(2, 3); five + five.
// The program means exactly the same thing.

Now compare:

let count = 0
const next = () => { count = count + 1; return count }
const y = next() + next()   // 1 + 2 = 3
// Rewrite it as const n = next(); n + n  ->  1 + 1 = 2. A different program!

next() is not referentially transparent: the same expression gives a different value each time, because it reads and changes hidden state. A function whose calls are always referentially transparent is called pure. In practice that means two things:

  1. Same arguments, same result. The result depends on nothing except the arguments (no globals, no clock, no randomness, no files).
  2. No observable effects. Calling it changes nothing the rest of the program can see (no mutation of its arguments or globals, no printing, no drawing).

Why care? Because a pure function can be understood by looking at it alone. You can test it by calling it with inputs and checking the output. You can call it twice, or zero times, or cache the result, and nothing breaks. This is the substitution model of evaluation: you evaluate a program by replacing names with their definitions, like algebra (add(2, 3) + add(2, 3) becomes 5 + 5 becomes 10). It only works when everything is referentially transparent.

From everyday programming: think of a unit test for a method that reads the clock, a global singleton or a database. Before you can test it you need mocks, fakes or dependency injection to take control of those hidden inputs. A pure function has no hidden inputs: everything it depends on is an argument, so the test passes the inputs and checks the output, nothing more. A spreadsheet is another familiar example: a cell such as =A1 * 2 is a pure function of other cells, which is why the spreadsheet can recompute any cell at any time and always get the same answer.

No compiler checks purity for you, in JavaScript, Scala or F#. In all three it is a discipline. In this course the tests and the purity audit help you keep it.

Exercise in prose: pure or not?

Before reading the answers, decide for each function: pure or impure? If impure, which of the two rules does it break?

const a = (xs) => xs.length                      // (a)
const b = (xs) => { xs.push(0); return xs }      // (b)
const c = () => Date.now()                       // (c)
const d = (p) => ({ ...p, x: p.x + 1 })          // (d)
const e = (msg) => { console.log(msg); return msg } // (e)
const f = (xs) => xs.toSorted()                   // (f)
const g = (xs) => xs.sort()                       // (g)
const h = (n) => { throw new Error('no') }        // (h)
Answers
  • (a) pure. Result depends only on xs, nothing changes.
  • (b) impure. It mutates its argument. The caller's array has grown, and anyone else holding it sees the change. (Same input array, second call: a different result.)
  • (c) impure. No arguments, yet a different result every millisecond: a hidden input (the clock).
  • (d) pure. It builds a new object; p is untouched.
  • (e) impure. It returns its argument unchanged, but printing is an effect the outside world can observe. Replacing e('hi') with 'hi' changes what the program does.
  • (f) pure. toSorted returns a new sorted array (ES2023).
  • (g) impure. sort sorts in place and returns the same array. This is a classic bug source in JavaScript.
  • (h) debatable. It is deterministic and changes nothing, but it does not return a value. Many people count exceptions as an effect. In this course we avoid throwing in game logic: our rule functions are total (they return a value for every input), which you will see in Module 3.

const is not immutability

In JavaScript, const means this name will always refer to the same value. It says nothing about whether the value can change:

const xs = [1, 2]
xs.push(3)        // allowed! xs is still the same array, which now has 3 elements
xs = [9]          // TypeError: Assignment to constant variable.

So there are two different things:

Can the name point somewhere else? Can the value change?
JS let yes yes (if it is an object/array)
JS const no yes (if it is an object/array)
JS const + frozen value no no
Scala val + List, case class no no
F# let + list, record no no

From everyday programming: Java's final and C#'s readonly behave like const. final List<String> names = new ArrayList<>() cannot be made to point at another list, but names.add("Ada") still changes the list it points at. Immutability comes from the data type, not from the keyword on the name.

The same holds in the other tracks. In Scala, val buf = ListBuffer(1) cannot be reassigned, but buf += 2 still mutates it; the immutable List and case classes are what make the data unchangeable. F# is stricter: let bindings cannot be reassigned at all unless declared let mutable, and lists and records are immutable.

Freezing in JavaScript

Object.freeze(obj) makes an object (or array) read-only: assigning to a property or pushing an element throws in strict mode, which ES modules always are.

const p = Object.freeze({ x: 1, y: 2 })
p.x = 5            // TypeError in a module: Cannot assign to read only property 'x'

But freeze is shallow. It freezes the object's own properties, not the objects they point to:

const game = Object.freeze({ snake: [{ x: 1, y: 1 }] })
game.snake = []          // TypeError: good
game.snake.push({x: 2})  // works! The array inside is not frozen.

The tests in this course deep-freeze every input they hand to your functions. If your code accidentally mutates its input, it does not silently corrupt the test; it throws a TypeError at the exact line that tried. When you see Cannot add property 3, object is not extensible or Cannot assign to read only property, you have found a mutation. You will write deepFreeze yourself in this module.

Persistent data and structural sharing

If we never change data, do we copy everything all the time? No. Since nobody can change the old value, the new value may share the parts that did not change.

 before:  snake ----> [ H0 , B1 , B2 ]       (an array of three point objects)
 after:   snake' ---> [ H1 , H0 , B1 ]       (a new array...)
                              |    |
                              +----+--- ...pointing at the very same point objects

In JavaScript, [newHead, ...rest] creates a new array (copying the references, which is cheap for small arrays) but shares every point object. In Scala and F#, newHead :: rest is even cheaper: the new list is one new cell pointing to the old list, which is shared entirely. Data structures designed for this are called persistent: old versions stay valid after you "update" them. Sharing is only safe because nobody mutates; that is why immutability and persistence go together.

From everyday programming: Git works this way. A commit is an immutable snapshot of your project. A new commit stores only what changed and points to the unchanged files of earlier commits, so it is cheap; and because no commit is ever modified, every old version stays valid and you can check it out at any time.

In the Scala track, List, Vector and Map are all persistent: xs :+ x on a Vector returns a new vector that shares almost all of its structure with xs. F#'s list and Map behave the same way.

Making a changed copy

The core move of this whole course: take a record, and produce a new record that differs in a few fields. Each language has a built-in syntax for it. Here with a small example record (not from the game):

JavaScript

const ada = { name: 'Ada', hp: 10, level: 3 }
const hurt = { ...ada, hp: ada.hp - 4 }   // { name: 'Ada', hp: 6, level: 3 }; ada is unchanged

Scala

final case class Hero(name: String, hp: Int, level: Int)
val ada  = Hero("Ada", 10, 3)
val hurt = ada.copy(hp = ada.hp - 4)       // Hero(Ada,6,3); ada is unchanged

F#

type Hero = { Name: string; Hp: int; Level: int }
let ada  = { Name = "Ada"; Hp = 10; Level = 3 }
let hurt = { ada with Hp = ada.Hp - 4 }    // { Name = "Ada"; Hp = 6; Level = 3 }

From everyday programming: in object-oriented code you might write hero.setHp(hero.getHp() - 4). The object changes, and every part of the program that holds a reference to hero sees the new value, whether it expected to or not; "who changed this?" bugs come from exactly that. With a changed copy, ada stays as it was, and code that should see the hurt hero has to be handed hurt. You already know one type that works like this: strings in Java, C#, Python and JavaScript are immutable, so s.toUpperCase() returns a new string and leaves s alone. That is why you can pass strings around without worrying who else holds them.

A Scala case class and an F# record are immutable records: their fields cannot be reassigned, so copy and with are the only way to get a changed version.

Note the naming convention: F# record fields are PascalCase (Hp, and later NextDir), where JS and Scala use camelCase (hp, nextDir).

Watch out in JS: spread is shallow, like freeze. { ...game, snake: game.snake } shares the same snake array. That is fine as long as nobody mutates it, which is exactly our rule.

For arrays in JavaScript, learn which methods build a new array and which change the old one:

Builds a new value (use these) Mutates in place (banned by the purity audit)
map, filter, reduce, slice, concat, [...xs, x], [x, ...xs] push, pop, shift, unshift, splice
toSorted, toReversed, with(i, v) sort, reverse, xs[i] = v
some, every, find, includes, Array.from

Loops without reassignment

A for loop needs a counter that changes, so it needs let. Without let you express the loop differently: as a transformation of a whole collection, as a fold, or as recursion. Three operations cover most of the loops you have ever written. Each takes a small function that says what to do with one element (the next section, "Functions are values", looks at passing functions around), does the looping itself, and returns a new array or value. The input array is left untouched.

  • map(f) calls f on every element and returns a new array of the results: same length, same order. [1, 2, 3].map((x) => x * 10) is [10, 20, 30].
  • filter(p) keeps the elements for which p returns true. A function that returns a boolean, like p, is called a predicate. [1, 2, 3, 4].filter((x) => x % 2 === 0) is [2, 4].
  • reduce(f, init), in general called a fold, combines all elements into one value. It starts with an accumulator equal to init, and for each element computes the next accumulator as f(acc, x). The last accumulator is the result. [1, 2, 3].reduce((acc, x) => acc + x, 0) computes ((0 + 1) + 2) + 3, which is 6.

Here is one computation written both ways:

// With a loop: a counter and a total that change on every step.
let total = 0
for (let i = 0; i < xs.length; i++) {
  if (xs[i] % 2 === 0) total = total + xs[i] * xs[i]
}

// Without: the sum of the squares of the even numbers, no loop and no let.
const sumEvenSquares = (xs) => xs.filter((x) => x % 2 === 0).map((x) => x * x).reduce((a, b) => a + b, 0)

Read the second version as a pipeline: keep the even numbers, square each one, add them up. Each step's input is the previous step's output, and nothing is changed along the way. Notice that the loop's total became reduce's accumulator: any loop of the shape "start with a value, update it once per element, use the final value" is a fold, whatever it computes.

From everyday programming: if you have written SQL, you know this style. SELECT x * x FROM xs WHERE x % 2 = 0 is a filter (WHERE) followed by a map (SELECT), and wrapping it in SUM(...) is a fold. You say what you want, and the database does the looping. C#'s LINQ (Where, Select, Aggregate), Java streams (filter, map, reduce) and Python's list comprehensions are the same three ideas under other names.

In the Scala track the three are xs.map(f), xs.filter(p) and xs.foldLeft(init)(f); in F#, List.map f xs, List.filter p xs and List.fold f init xs. JavaScript's reduceRight folds from the end of the array (Scala foldRight, F# List.foldBack). One trap: JavaScript's reduce without an initial value throws on an empty array (so does Scala's reduce). Always pass the initial value. (Fold (Wikipedia) has pictures of both directions.)

Array.from({ length: n }, (_, i) => ...) builds an array of length n by calling a function with each index. Array.from is worth looking up now. (In the Scala track, List.tabulate does the same.)

Functions are values

A function is a value like any other. You can store it in a const, pass it as an argument, and return it from another function:

JavaScript

const twice = (f) => (x) => f(f(x))   // takes a function, returns a function
const addThree = (n) => n + 3
twice(addThree)(10)                    // 16

Scala

def twice(f: Int => Int): Int => Int = x => f(f(x))
val addThree = (n: Int) => n + 3
twice(addThree)(10)                    // 16

F#

let twice f = fun x -> f (f x)
let addThree n = n + 3
twice addThree 10                      // 16

twice returns a new function that still has access to the f it was given, even after twice itself has returned. A function that captures values from the place where it was created is called a closure. A function that takes or returns another function, like twice, map or filter, is called a higher-order function.

From everyday programming: you have passed functions as values whenever you wrote a callback. button.addEventListener('click', onClick) hands the function onClick to the browser, which calls it later; setInterval(step, 150) does the same with a timer; a comparator passed to a sort method is a function that the sort calls whenever it needs to compare two elements. map and filter take callbacks in exactly the same way. The difference in this course is what the callbacks do: they return a result instead of changing something.

In F#, every function of several arguments is curried by default: let add a b = a + b has type int -> int -> int, and add 3 is a function waiting for the second number. That is why F# library functions put the data last: List.map f xs can be partially applied as List.map f and used in a pipeline.

This module's contains(xs, p, eq) takes a function as its third argument. Why not compare with ===? Because in JavaScript === on objects compares identity: {x: 1} === {x: 1} is false. Passing eq lets the caller decide what "equal" means, for instance "same x and same y".

Composition

Programs in this course are mostly small functions plugged together. Two ways of plugging:

  • pipe (left to right): start with a value and push it through functions in reading order. pipe(x, f, g) is g(f(x)).
  • compose (right to left, like maths): compose(g, f) is the function x => g(f(x)), read "g after f".
const inc = (x) => x + 1
const double = (x) => x * 2
// pipe(3, inc, double)      -> double(inc(3)) = 8
// compose(double, inc)(3)   -> double(inc(3)) = 8
// compose(inc, double)(3)   -> inc(double(3)) = 7

JavaScript has neither built in; you write both in this module (Exercises 1.4 and 1.5). Scala and F# do have them:

Scala

val inc    = (x: Int) => x + 1
val double = (x: Int) => x * 2
(inc andThen double)(3)    // 8: first inc, then double (like pipe)
(double compose inc)(3)    // 8: double after inc (like compose)
3.pipe(inc).pipe(double)   // 8, needs: import scala.util.chaining.*

F#

let inc x = x + 1
let double x = x * 2
3 |> inc |> double         // 8: the pipe operator, value first
(inc >> double) 3          // 8: forward composition, like andThen
(double << inc) 3          // 8: backward composition, like compose

Side by side: Scala's f andThen g is F#'s f >> g and the JS pipe order; Scala's g compose f is F#'s g << f and the JS compose order. The F# pipe x |> f is f x written backwards, which makes long chains read top to bottom, like a chain of method calls x.f().g().

From everyday programming: a shell pipeline such as cat log.txt | grep ERROR | sort | uniq is pipe: a value goes in on the left and passes through each command in reading order. Each command reads its input and writes a new output; none of them edits log.txt.

This is why the Scala and F# tracks have a smaller Module 1: pipe, compose and immutable data are built in. Their tests cover range, dropLast and contains; the composition exercise is a short practice session in the REPL instead.

Exercises

All functions here must be pure: no mutation (inputs are deep-frozen in the JS tests, so mutation throws), no reassignment.

About test names. The test titles quoted under "Tests" are the JavaScript ones; the JS runner prints them with the module in front (m01 range(0) is empty). The Scala suite uses the same titles. The F# titles use F# call syntax (range 0 is empty). Scala and F# have no tests for pipe, compose and deepFreeze, which are JS-only exercises. Failing tests are reported by name when you run the module's tests; to read all titles, open scala/test/M01Util.test.scala or fsharp/tests/M01Util.fs. (Module 1 has no fixture-based tests.)

Exercise 1.1 — range

range(n) returns the numbers 0, 1, ..., n-1 in order; range(0) is empty. You will use it in Module 4 to list every cell of the board.

JavaScript

export const range = (n) => ...      // range(3) -> [0, 1, 2]

Scala

def range(n: Int): List[Int]         // range(3) == List(0, 1, 2)

F#

let range (n: int) : int list        // range 3 = [0; 1; 2]

Tests: range(0) is empty, range(3) counts from zero up to n-1.

Watch out: no for (let i ...) in JS. Think "build an array of length n from its indices".

Exercise 1.2 — dropLast

dropLast(xs) returns xs without its last element. The empty list stays empty. It must never modify xs. You will use it in Module 3: a moving snake loses its last segment.

JavaScript

export const dropLast = (xs) => ...  // dropLast([1, 2, 3]) -> [1, 2]; dropLast([]) -> []

Scala

def dropLast[A](xs: List[A]): List[A]

F#

let dropLast (xs: 'a list) : 'a list

Tests: dropLast of an empty list is empty, dropLast removes only the last element, dropLast leaves its input untouched (the input is frozen in JS).

Watch out: the empty case. In Scala, List.empty.init throws. In F#, List.init is something else entirely (it builds a list from a length and a function). A function that throws on some inputs is called partial; we want total functions.

Exercise 1.3 — contains

contains(xs, p, eq) is true if some element x of xs satisfies eq(x, p). In Module 3 you will ask "does the snake's body contain this point?", where points are compared by their coordinates.

JavaScript

export const contains = (xs, p, eq) => ...   // contains([1, 2, 3], 5, sameParity) -> true

Scala

def contains[A](xs: List[A], p: A, eq: (A, A) => Boolean): Boolean

F#

let contains (xs: 'a list) (p: 'a) (eq: 'a -> 'a -> bool) : bool

Tests: contains finds an element using the supplied equality (with sameParity, 5 "equals" 1 and 3), contains is false when no element is equal, contains is false for an empty list, contains compares structurally when given a structural equality.

Watch out: the argument order of eq. The doc comment says eq(x, p): the list element first.

Exercise 1.4 — pipe (JS only)

pipe(x, ...fns) threads x through the functions from left to right. With no functions it returns x.

JavaScript

export const pipe = (x, ...fns) => ...   // pipe(2, x => x + 1, x => x * 10) -> 30; pipe(5) -> 5

Tests: pipe threads a value through functions left to right, pipe with no functions returns the value.

Scala / F# practice (no tests). Open a REPL (scala-cli repl or dotnet fsi). Define inc, double and square, and predict, before evaluating, the results of: Scala (inc andThen double andThen square)(1) and (inc compose double compose square)(1); F# 1 |> inc |> double |> square and (inc << double << square) 1. Check your predictions.

Exercise 1.5 — compose (JS only)

compose(...fns) returns a function that applies the functions right to left. compose() with no functions is the identity function.

JavaScript

export const compose = (...fns) => ...   // compose(x => x * 10, x => x + 1)(2) -> 30; compose()(5) -> 5

Tests: compose applies functions right to left, compose with no functions is the identity.

Exercise 1.6 — deepFreeze (JS only)

deepFreeze(obj) freezes obj and everything reachable from it, then returns the same object. Two situations make it interesting:

  • An already-frozen parent with unfrozen children. You must still go into it. (Test: deepFreeze reaches unfrozen children of an already-frozen parent.)
  • Cycles. o.child.parent === o. A naive recursion never ends. (Test: deepFreeze handles cyclic objects.)

JavaScript

export const deepFreeze = (obj) => ...   // returns obj itself, frozen all the way down

Other tests: deepFreeze freezes nested objects and arrays, deepFreeze returns the same object it was given.

Watch out: typeof null === 'object'. And you may not keep a mutable "already seen" set in a let. How else could a recursive call know where it has already been?

One honest remark: Object.freeze itself changes the object (it flips it to read-only). That is the one deliberate "mutation" in this module, and it only ever removes the ability to change things.

Run

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

When green, also run the full suite once (./test.sh) to check the purity audit is happy with util.

Hints

Exercise 1.1 (range) — nudge

Each language has a function that builds a collection of a given length from the index; for JavaScript, "Loops without reassignment" mentions it. In Scala and F# there is even a ready-made range syntax.

Exercise 1.1 (range) — stronger hint

JS: Array.from takes an "array-like" object (anything with a length) and a mapping function (element, index) => .... Scala: 0 until n is a Range; it has .toList. F#: [ a .. b ] is a list literal for a range (what is b when you want n numbers starting at 0?), and List.init builds from a length and a function.

Exercise 1.1 (range) — near-solution (try the others first) 
export const range = (n) => Array.from({ length: ___ }, (___, i) => ___)

def range(n: Int): List[Int] = (0 until ___).___

let range (n: int) : int list = List.init ___ (fun i -> ___)
Exercise 1.2 (dropLast) — nudge

Which non-mutating method gives you "a piece of the array from here to there"? Can its "to" index count from the end?

Exercise 1.2 (dropLast) — stronger hint

JS: slice(start, end) returns a new array and accepts negative indices, counted from the end. Try [].slice(0, -1) in a Node REPL. Scala: dropRight exists and is total; or pattern-match on the list. F#: pattern matching on the list is the clearest. (A match checks which shape a value has and names its parts: [] is the empty list, [ _ ] a list of exactly one element, and x :: rest a list whose first element is x, followed by the list rest. Module 2 explains pattern matching in general.) Which three shapes can a list have that matter here? (empty, exactly one element, more than one)

Exercise 1.2 (dropLast) — near-solution (try the others first) 
export const dropLast = (xs) => xs.slice(___, ___)

def dropLast[A](xs: List[A]): List[A] = xs.dropRight(___)

let rec dropLast (xs: 'a list) : 'a list =
    match xs with
    | [] | [ _ ] -> ___
    | x :: rest -> ___ :: ___

Note the rec in F#: recursive functions must say so.

Exercise 1.3 (contains) — nudge

The question "is there some element such that ...?" has a name in every collection library.

Exercise 1.3 (contains) — stronger hint

JS Array.prototype.some, Scala exists, F# List.exists. Each takes a predicate (a function element → boolean). Build that predicate from eq and p.

Exercise 1.3 (contains) — near-solution (try the others first) 
export const contains = (xs, p, eq) => xs.some((x) => ___)

def contains[A](xs: List[A], p: A, eq: (A, A) => Boolean): Boolean = xs.exists(x => ___)

let contains (xs: 'a list) (p: 'a) (eq: 'a -> 'a -> bool) : bool = xs |> List.exists (fun x -> ___)
Exercise 1.4 (pipe) — nudge

You have a starting value and a list of functions. You want to go through the list, carrying a "current value" along. Which list operation carries an accumulator through a list?

Exercise 1.4 (pipe) — stronger hint

It is a fold: fns.reduce(step, x). The accumulator is the current value; each step applies the next function to it. With no functions, reduce returns the initial value, which is exactly the required behaviour.

Exercise 1.4 (pipe) — near-solution (try the others first) 
export const pipe = (x, ...fns) => fns.reduce((acc, f) => ___, ___)
Exercise 1.5 (compose) — nudge

compose returns a function. Inside that function you have the argument and the list of functions. How is that like pipe, and in which direction must you walk the list?

Exercise 1.5 (compose) — stronger hint

compose(f, g, h)(x) is f(g(h(x))): apply the last function first. reduceRight walks an array from the end. (Alternatively: toReversed() and reuse your pipe.)

Exercise 1.5 (compose) — near-solution (try the others first) 
export const compose = (...fns) => (x) => fns.reduceRight((acc, f) => ___, ___)
Exercise 1.6 (deepFreeze) — nudge

Write the simple version first: freeze the object, then call deepFreeze on each of its values (Object.values works for arrays too). Then think about the two stopping conditions: values that are not objects, and objects you are already inside of.

Exercise 1.6 (deepFreeze) — stronger hint

Do not use Object.isFrozen to decide whether to stop: that is exactly what breaks for an already-frozen parent with unfrozen children. To detect a cycle without mutable state, give the function a second parameter with a default value: the list of ancestors (the objects on the path from the root down to here). A cycle means the current object is one of its own ancestors. Each recursive call passes a new list with the current object added.

Exercise 1.6 (deepFreeze) — near-solution (try the others first) 
export const deepFreeze = (obj, ancestors = []) => {
  if (obj === null || typeof obj !== ___ || ancestors.includes(___)) return obj
  Object.freeze(obj)
  Object.values(obj).forEach((v) => deepFreeze(v, [___, ___]))
  return ___
}

Check your understanding

  1. Is const now = () => Date.now() referentially transparent? Is the expression now (without calling it)? What is the difference?
  2. Predict: const a = Object.freeze({ xs: [1] }); a.xs.push(2); a.xs.length. What does it evaluate to, and why? What would happen with deepFreeze instead?
  3. { ...state, score: state.score + 1 } shares the snake array between the old and the new state. Why is that safe here, and what single line elsewhere in the program would make it unsafe?
  4. Predict compose(pipe)(3) and pipe(3, compose()). Explain using the definitions, not by running them.
  5. In F#, why is it List.map f xs (data last) while in JS our functions take the data first? What does the F# order make easy?
  6. Your dropLast passes the tests. Would it still be correct if the tests did not freeze the input? How could you be sure it never mutates, other than through tests?
  7. The purity audit bans .sort( but you may use .toSorted(). Explain in one sentence what the difference is, in terms of referential transparency.
  8. Why does contains take an eq parameter in JavaScript? (In the Scala and F# tracks, == and = compare case classes and records field by field, so _ == _ or (=) would do; Module 2 explains the difference.)

In production

  • Immer (immerjs.github.io/immer) lets JavaScript developers write code that looks like mutation inside a callback, and turns it into a new immutable value with structural sharing. Redux Toolkit uses it under the hood.
  • Immutable.js (immutable-js.com) provides persistent List and Map types for JavaScript, like Scala's and F#'s collections.
  • Scala and F# collections are persistent by default: Scala's immutable collections, F#'s list, Map and Set.
  • Clojure made persistent data structures the default for a whole language; Rich Hickey's talk below explains why.

Further reading

Reference in New Issue View Git Blame Copy Permalink