A pure functional data structure is immutable and operated on only through pure functions. Operations return new values without changing existing data, so earlier references remain valid. section 3.1 section 3.6
A singly linked list makes the design concrete: Nil represents an empty list, while Cons stores a head and a tail. Pattern matching exposes these constructors for recursive processing. section 3.1 section 3.6
Sharing an immutable list
Given xs, prepending 1 returns Cons(1, xs) without copying xs. Removing the first element returns xs itself. These operations preserve the original list through persistence, also called structural sharing. Prepending and taking the tail can therefore avoid copying, while replacing a tail near the end may require copying preceding Cons objects. section 3.3 section 3.3.1
Typical operations illustrate the trade-offs of immutable structure:
- Implement tail to return every element after the first, handling Nil explicitly. section 3.3
- Implement setHead by constructing a list with a replacement first element. section 3.3
- Implement init to return all but the last element and examine why it cannot run in constant time. section 3.3.1
Listing 3.1 Singly linked lists
package fpinscala.datastructures
enum List[+A]: #1
case Nil #2
case Cons(head: A, tail: List[A]) #3
object List: #4
def apply[A](as: A*): List[A] = #5
if as.isEmpty then Nil
else Cons(as.head, apply(as.tail*))
The list definition shows the two constructors and the companion-object apply function used to build lists recursively. section 3.1
