Functional data structures

In the previous lesson, we saw that pure functions do not cause side effects or change their inputs. A functional data structure follows that rule for its data: its operations use pure functions. Its values are immutable, meaning no operation can edit them in place. To add an item, an operation returns a new list.

Scala's enum lists a type's possible forms. For one concrete example, use an integer-only list with two forms: Nil means empty, and Cons(head, tail) is one cell holding a first value (head) and another list (tail). This lets a new cell point to an existing list.

old still holds the list containing 2. next is one new cell for 1 followed by the exact list in old; the existing cell is not copied or changed. If a shared cell could be edited, both lists would reflect that edit. Because IntList cells are immutable, both versions remain valid. A functional update can reuse an unchanged tail without copying every element.

Last lesson showed that a new list can reuse an unchanged old list as its tail. To see what List(1, 2, 3) is made from, we’ll use this chapter’s custom List, not Scala’s standard-library List. A constructor is a named form for building a value. This type has two: Nil builds the empty list; Cons builds a nonempty list from one head (element) and a tail (another List).

In List[A], A is a type parameter, a placeholder for the element type. The same definition can describe List[Int] and List[String]; it is polymorphic, meaning it works with different element types.

Read numbers from the outside in. The first Cons holds 1; its tail is another list starting with 2, then 3, then Nil. Each Cons stores one element and the next list, not every later element at once. Nil means the list is empty, not that a value is missing. Every list is either Nil or Cons(head, tail), where the tail is another list.

The previous lesson showed that the custom List has two shapes: Nil, or Cons(head, tail). How can a function choose an answer for either shape? Pattern matching checks which constructor built a value and selects the matching case. A case pairs a pattern with an answer; a pattern describes the shape it checks. In Cons(head, tail), head and tail bind, meaning they receive the values stored in that Cons. A recursive function calls itself; for a list, it can continue with the shorter tail.

Nil returns 0 and stops, so it is the base case, the branch that ends the recursion. The Cons branch is the recursive case, the branch that calls sum again. It adds the current head to sum(tail). Each tail is shorter than the list it came from, so repeated calls eventually reach Nil.

The custom List has only Nil and Cons, so these cases cover every shape. A match that covers every possible constructor is exhaustive. Scala checks cases in order and uses the first matching one. If none matches, Scala raises MatchError, an error meaning no case fit that value. Patterns read the list; they do not change it. Match every constructor, stop at Nil, and recurse only on smaller data.

Last lesson, pattern matching let us read a nonempty list as Cons(head, tail). The answer to this lesson's question is no: adding one item need not copy the tail. Prepend means to put an item at the front.

Each Cons expression creates one new cell for its first value. Both new cells hold the same xs object as their tail, so they reuse the old list's cells. This reuse of unchanged parts is called structural sharing.

The original xs still contains 2 followed by 3, and both new lists remain usable. A list is persistent when an operation can make a new version while leaving earlier versions unchanged. Sharing is safe because no operation can edit the shared tail in place.

The previous lesson showed that two immutable lists can point to the same unchanged tail without either list changing. A Cons cell stores a head, the first item, and a tail, the remaining list; Nil means no items. Prepending means adding at the front. Here, drop(as, n) means return the list after skipping n items. Constant time means a fixed amount of work, no matter how many cells follow.

Prepending 0 creates one new Cons and points it at the existing xs. tail reads the first cell and returns its existing rest list; it does not traverse the rest of xs. Each operation does a fixed number of steps, so each is constant time.

drop takes time in proportion to the number of items it skips. If it reaches Nil first, it returns Nil. Each Cons here points to one next cell; a list with that shape is called singly linked. These costs follow from that shape, and another data structure may make different operations cheaper.

Last lesson, drop followed links from the front and returned the tail it reached. Here List is the chapter's custom list: Cons(head, tail) holds one item and the rest of the list, while Nil marks the end. init returns every item except the last. Those kept items are the prefix, the part before the last item. append joins two lists, placing the second after the first.

For Cons(1, Cons(2, Cons(3, Nil))), init should return Cons(1, Cons(2, Nil)). Editing the Cons that holds 2 so its tail is Nil would also change the original list and lose 3. Instead, init builds Cons(2, Nil), then Cons(1, Cons(2, Nil)). It rebuilds the whole prefix, so the work grows with the number of kept items.

When the first input, a1, is Nil, the function returns the second input, a2, unchanged. Otherwise, it saves one head and calls itself on the tail. As those calls return, each saved head gets a new Cons. The result creates a new Cons for every item of a1, then points to a2 unchanged. Its work depends on the length of a1, not a2.

Last lesson, init rebuilt earlier Cons values because immutable lists cannot change their tails. A list is Nil (empty) or Cons(head, tail) (one item followed by the rest). A fold turns that shape into one result: a base result for Nil and a combining function for each Cons. Recursion means a function calls itself. foldRight follows each tail to Nil, then combines each head with the tail's result. foldRight is a higher-order function because it takes another function. A type names a kind of value. Here, A names items and B names results. Int holds whole numbers; String holds text. sum adds numbers, product multiplies them, and text joins their digits.

The sum trace explains the other calls. Product uses base 1 and multiplication. Text uses an empty-string base; toString converts each integer, and + joins it to the tail text, yielding "12". Thus the same List[Int] folds to String; B need not equal A. Folds can also build lists, leading to four common operations:

foldRight keeps the Nil/Cons traversal while its base and combining function choose the result. The four operations package common output shapes.

Last lesson showed foldRight using one recursive list walk for different jobs: the empty list gives a starting result, and each cell combines its head with the folded tail. Now we trace the direct version at run time. Evaluation order is the order in which these calculations happen.

The call stack is memory that tracks function calls that have not finished. Each waiting call uses some of that space. A long list can need more space than available. The program then reports a stack overflow, an error caused by running out of call-stack space. This warning applies to the chapter's direct implementation, not every function named foldRight.

Composition means using one function's output as another's input. A pass is one complete visit through a list. If one function builds a temporary list for the next, that result is an intermediate list. The next function may make another pass. Early termination means stopping as soon as the answer is known. A chain that must finish a pass can delay that stop. A focused recursive function can help when extra passes or stopping early matter. So equal answers can still require different work at run time: this direct foldRight can grow the call stack, and composed functions can add passes or delay stopping.

Last lesson traced the direct foldRight: it reached the end before combining anything, leaving calls waiting. foldLeft starts with the first item and carries an accumulator, the result so far, into the next call. Its combining function, f, uses the accumulator and current item to produce the next result.

The call stack keeps track of unfinished function calls. A function is tail recursive when its last action is to call itself, with no work left afterward. In the Cons case, foldLeft passes the updated result straight to its next call. Scala can run this shape without keeping one unfinished call per item. A fold is stack safe when a long list does not overflow the call stack. This foldLeft can be stack safe; other folds are not automatically so.

An order-sensitive combining function produces a different result when the same inputs are combined in a different order. Subtraction is one example. With items 1, 2, 3 and starting result 0, foldLeft calculates ((0 - 1) - 2) - 3 = -6; foldRight calculates 1 - (2 - (3 - 0)) = 2. The folds differ because they combine in opposite orders.

Last lesson, foldLeft followed List's Nil and Cons cases while carrying a result. Tree functions use the same case-by-case plan. A constructor is a named case that builds a value. ADT here means algebraic data type, not abstract data type. It fixes the allowed constructors and their stored data. The constructors form a closed set, so no other case belongs to Tree. Tree has two constructors: Leaf stores a value and has no children; Branch stores two child trees. With two children per branch, Tree is a binary tree. Recursion means a function calls itself on smaller pieces.

Scala's enum lists the allowed cases. A type parameter stands for a type; A here is the type of each Leaf value. A match checks which constructor made the current value. A method is a function attached to a type; inside it, this means the current tree. In a case, _ tells Scala to ignore a value. The size method counts each Leaf and Branch, so it can ignore a Leaf's value.

this match checks which constructor made the current tree. A Leaf contributes 1. A Branch contributes 1 for itself, plus the sizes of left and right. Each name holds one child tree, so the method calls itself for both children. The calls stop at Leaf. Adding their results counts every Leaf and Branch.

Scala can write the same type with a trait, a parent type shared by its cases. sealed requires every case to be declared in the same source file, so another file cannot add a third case. extends Tree[A] marks Leaf and Branch as Tree cases.

Both forms allow the same Leaf and Branch cases, with immutable stored values. Only Scala's way of writing them changes. Define the shapes first, then give each shape its part of the operation.

Last lesson introduced two tree shapes: Leaf(value) holds one value, and Branch(left, right) holds two child trees. Tree functions handle a leaf or recurse into both children of a branch. How can the same walk count leaves and branches (size), find the largest leaf value (maximum), measure the longest path from the top of the tree to a leaf (depth), or change each leaf value (map)? A tree fold keeps that walk but asks its caller for two functions. The leaf function turns each leaf value into a result. The branch function combines the results from the two child trees into a result for their branch.

fold calls onLeaf with a leaf's value. For a branch, it first folds each child, then gives both results to onBranch. size counts each leaf and branch; maximum starts with a leaf value and compares child results; map changes each leaf before rebuilding branches. For depth, a leaf starts at zero edges, and each branch adds one edge to the longer child path.

Each call to size, maximum, depth, or map still walks the tree; fold shares the recursion code. At each branch, a tree fold combines two child results. A list foldLeft carries one running result, called an accumulator.