Functional Data Structures (Persistence & sharing)

Persistent structures reuse unchanged nodes so older versions remain valid—common in functional languages; simulated in interviews with path copying for trees. Immutable snapshots simplify concurrency reasoning.

Why this shows up in the real world

Git stores immutable object graphs with new commits pointing to reused blobs. Event sourcing replays immutable logs.

Core idea (explained for students)

Path copying updates only nodes from root to changed leaf; siblings are shared. Trade extra memory for cheap history branches.

Try this in Python

def push_version(stk: tuple[int, ...], x: int) -> tuple[int, ...]:
    return stk + (x,)


s1 = ()
s2 = push_version(s1, 1)
s3 = push_version(s2, 2)
print(s1, s2, s3)

Common mistakes

• Confusing persistence with memoization caches—different goals.
• Copying entire containers each update—loses structural sharing benefits.

Key takeaways

• Reach for persistence when you need time travel or forkable state.
• In Python, tuple of immutables models lightweight snapshots.