Structural sharing

As explained in Functional Programming in Scala, Second Edition

Structural sharing is the reuse of unchanged substructures between immutable data structures instead of copying them.

Structural sharing reuses unchanged substructures between immutable data structures instead of copying them. In a singly linked list, prepending 1 returns Cons(1, xs), reusing xs; removing the head returns its tail. Existing references remain unchanged, so the structure is persistent. section 3.3 section 3.6

Sharing improves some operations while imposing copying costs where the linked structure cannot be reused:

• tail can return the existing tail in constant time, without copying. section 3.3
• drop and dropWhile copy only the portion they traverse, rather than the entire list. section 3.3.1
• Appending a1 to a2 copies the nodes of a1, then points the result at a2. section 3.3.1
• Replacing the tail near the end, as init requires, copies every preceding Cons; efficient functional structures balance such trade-offs across operations. section 3.3.1 section 3.6

Appending by sharing the suffix

def append[A](a1: List[A], a2: List[A]): List[A] = a1 match case Nil => a2 case Cons(h, t) => Cons(h, append(t, a2)) The recursion rebuilds only a1. When a1 is exhausted, the result reuses a2 directly. section 3.3.1

Figure 3.3 Data sharing of lists

Use the list-sharing figure to visualize how immutable list results retain unchanged structure. section 3.3

How Functional Programming in Scala, Second Edition covers it

How deep it goes

Explains reuse, persistence, runtime costs, and copying limits through linked-list operations, but defers alternative data-structure implementations.

Examples

Uses Cons and Nil lists, tail, drop, dropWhile, append, and init to expose reuse and copying behavior.

What it assumes

Assumes immutable data and singly linked lists while building from algebraic data types, pattern matching, and pure functions.

What you can do after

Apply structural sharing by implementing immutable list operations that reuse available substructures and copy only necessary prefixes.

How it connects

Connects immutable data structures, persistent data structures, singly linked lists, algebraic data types, and recursion.

liveBookmanning.com

Read Functional Programming in Scala, Second Edition on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Data-Oriented Programming: Reduce software complexityStructural sharing is a data-management technique in which related versions reuse unchanged portions of the same underlying structure.
• 

  liveBookmanning.com
  Grokking SimplicityStructural sharing is a data-structure technique in which multiple versions reuse references to common portions of their representation.

Compare how 3 books explain structural sharing →

Related concepts

• persistent data structureused by · A persistent data structure preserves access to previous versions because updates create new versions without modifying existing ones.
• shallow copyproduced by · A shallow copy duplicates a data structure’s outer container while retaining references to its nested values rather than copying them recursively.
• immutable collectionuses · An immutable collection is a collection whose membership and contents cannot be changed after creation.
• hierarchyuses · A hierarchy is an organization of entities into nested or ordered levels connected by parent-child, containment, or broader-to-narrower relationships.
• multi-version state managementproduces · Multi-version state management maintains multiple immutable versions of system data and advances a reference to select the current version.
• immutable functionused by · An immutable function is a deterministic function that does not modify its inputs or externally observable state.

This explainer was generated by Manning's knowledge graph from the text of Functional Programming in Scala, Second Edition. The section links point to the parts of the book it draws on.