Immutability & Persistent Data Structures

Overview

Immutability ensures data never changes:

• No mutation: Create new versions instead of modifying
• Referential transparency: Same data = same behavior
• Thread safety: Multiple threads can safely access
• Debugging: No unexpected state changes
• Performance: Structural sharing reduces memory

---

Immutable Collections

Tuples as Immutable Lists

# Tuples are immutable
data = (1, 2, 3)
print(data[0]) # 1

# Cannot modify
# data[0] = 10 # TypeError!

# Creating "new versions"
new_data = data + (4,) # Concatenation creates new tuple
print(data) # (1, 2, 3) - original unchanged
print(new_data) # (1, 2, 3, 4)

# Tuple unpacking
a, b, c = data
print(a, b, c) # 1 2 3

# Slicing creates new tuple
subset = data[1:]
print(subset) # (2, 3)

Frozenset for Immutable Sets

# Frozenset is immutable set
unique = frozenset([1, 2, 3, 2, 1])
print(unique) # frozenset({1, 2, 3})

# Cannot modify
# unique.add(4) # AttributeError!

# Set operations create new frozensets
a = frozenset([1, 2, 3])
b = frozenset([3, 4, 5])

union = a| b
print(union) # frozenset({1, 2, 3, 4, 5}) - new frozenset

intersection = a & b
print(intersection) # frozenset({3})

# Can use as dict keys (lists cannot)
key_value = {
 frozenset([1, 2]): "pair",
 frozenset([3, 4]): "another pair"
}

Immutable Mappings

from types import MappingProxyType

# MappingProxyType creates immutable view of dict
original = {'a': 1, 'b': 2}
immutable = MappingProxyType(original)

print(immutable['a']) # 1

# Cannot modify
# immutable['a'] = 10 # TypeError!

# But if original changes, immutable view reflects it
original['c'] = 3
print(immutable) # Shows the 'c': 3 change

---

Persistent Data Structures

Structural Sharing

# Creating "new versions" with minimal copying
def update_version(data, **updates):
 """Update data immutably using dict merge."""
 return {**data, **updates}

original = {'name': 'Alice', 'age': 30, 'city': 'NYC'}
updated = update_version(original, age=31)

print(original) # {'name': 'Alice', 'age': 30, 'city': 'NYC'} - unchanged
print(updated) # {'name': 'Alice', 'age': 31, 'city': 'NYC'}

# Both dicts share most data (structural sharing)
# Only the changed part differs

Immutable Records with namedtuple

from collections import namedtuple

# Define immutable record
User = namedtuple('User', ['name', 'age', 'email'])

user1 = User('Alice', 30, 'alice@example.com')
print(user1) # User(name='Alice', age=30, email='alice@example.com')

# Cannot modify
# user1.age = 31 # AttributeError!

# Create new version
user2 = user1._replace(age=31)
print(user1) # Original unchanged
print(user2) # New version with updated age

Dataclass with Frozen

from dataclasses import dataclass

@dataclass(frozen=True)
class Point:
 """Immutable point."""
 x: float
 y: float

 def translate(self, dx, dy):
 """Return new translated point."""
 return Point(self.x + dx, self.y + dy)

p1 = Point(1, 2)
# p1.x = 3 # FrozenInstanceError!

p2 = p1.translate(3, 4)
print(p1) # Point(x=1, y=2) - unchanged
print(p2) # Point(x=4, y=6) - new point

---

Working Immutably with Collections

Immutable List Operations

# Instead of modifying list, create new list
def immutable_append(lst, item):
 """Append without modifying original."""
 return lst + [item]

def immutable_remove(lst, item):
 """Remove without modifying original."""
 return [x for x in lst if x != item]

def immutable_update(lst, index, value):
 """Update element without modifying original."""
 return lst[:index] + [value] + lst[index+1:]

# Use it
data = [1, 2, 3]
data2 = immutable_append(data, 4)
data3 = immutable_remove(data2, 2)
data4 = immutable_update(data3, 0, 10)

print(data) # [1, 2, 3] - original unchanged
print(data2) # [1, 2, 3, 4]
print(data3) # [1, 3, 4]
print(data4) # [10, 3, 4]

Tree-Like Structures

# Immutable tree node
class TreeNode:
 def __init__(self, value, left=None, right=None):
 self.value = value
 self.left = left
 self.right = right

 def with_left(self, node):
 """Return new tree with different left child."""
 return TreeNode(self.value, left=node, right=self.right)

 def with_right(self, node):
 """Return new tree with different right child."""
 return TreeNode(self.value, left=self.left, right=node)

 def __repr__(self):
 return f"Tree({self.value}, {self.left}, {self.right})"

# Build tree immutably
tree1 = TreeNode(1)
tree2 = tree1.with_left(TreeNode(2))
tree3 = tree2.with_right(TreeNode(3))

# Structural sharing
print(tree1) # Tree(1, None, None)
print(tree2) # Tree(1, Tree(2, None, None), None)
print(tree3) # Tree(1, Tree(2, None, None), Tree(3, None, None))

-

Benefits of Immutability

Easier Testing

# Pure, testable functions with immutable data
def transform_config(config, overrides):
 """Transform config immutably."""
 return {**config, **overrides}

# Test easily
default_config = {'debug': False, 'timeout': 30}
test_config = transform_config(default_config, {'debug': True})

assert default_config == {'debug': False, 'timeout': 30} # Unchanged
assert test_config == {'debug': True, 'timeout': 30}

# No need for setup/teardown, config is never modified

Thread Safety

import threading

# Immutable data can be safely shared
shared_data = (1, 2, 3, 4, 5) # Immutable tuple

def worker(data):
 # Multiple threads can safely read
 total = sum(data)
 print(f"Sum: {total}")

threads = []
for _ in range(10):
 t = threading.Thread(target=worker, args=(shared_data,))
 t.start()
 threads.append(t)

for t in threads:
 t.join()

# No race conditions, no locks needed!
print(shared_data) # Still (1, 2, 3, 4, 5)

Structural Sharing Memory Efficiency

# Immutability + structural sharing = memory efficiency
def share_prefix(data, new_item):
 """Create new list sharing prefix."""
 return data + [new_item]

data1 = (1, 2, 3, 4, 5)
data2 = data1 + (6,) # Shares data1's elements
data3 = data2 + (7,) # Shares data1 and data2's elements

# In memory:
# data1 points to tuple [1,2,3,4,5]
# data2 creates tuple [1,2,3,4,5,6] - but can share prefix!
# data3 creates tuple [1,2,3,4,5,6,7] - shares prefix!

# Functional languages exploit this for efficiency

---

Real-World ML Example

Immutable Configuration

from dataclasses import dataclass

@dataclass(frozen=True)
class ModelConfig:
 """Immutable model configuration."""
 hidden_size: int
 num_layers: int
 dropout: float
 learning_rate: float

 def with_dropout(self, dropout):
 """Create config with different dropout."""
 return ModelConfig(
 hidden_size=self.hidden_size,
 num_layers=self.num_layers,
 dropout=dropout,
 learning_rate=self.learning_rate
)

# Use it
base_config = ModelConfig(
 hidden_size=256,
 num_layers=3,
 dropout=0.1,
 learning_rate=0.001
)

# Create variants without modifying original
config_high_dropout = base_config.with_dropout(0.5)

assert base_config.dropout == 0.1 # Original unchanged
assert config_high_dropout.dropout == 0.5

Immutable State in Training

from dataclasses import dataclass

@dataclass(frozen=True)
class TrainingState:
 """Immutable training state."""
 epoch: int
 loss: float
 accuracy: float
 best_accuracy: float = 0.0

 def update(self, loss, accuracy):
 """Create new state with updated metrics."""
 new_best = max(self.best_accuracy, accuracy)
 return TrainingState(
 epoch=self.epoch + 1,
 loss=loss,
 accuracy=accuracy,
 best_accuracy=new_best
)

# Training loop with immutable state
state = TrainingState(epoch=0, loss=0.0, accuracy=0.0)

for epoch in range(100):
 # Compute loss and accuracy
 loss = 0.5
 accuracy = 0.85

 # Create new state
 state = state.update(loss, accuracy)

 print(f"Epoch {state.epoch}: loss={state.loss}, acc={state.accuracy}")

---

Summary: Immutability Benefits

Benefit	Example
Thread safety	Multiple threads read safely
Predictability	Same data → same behavior
Testing	No setup/teardown needed
Debugging	No unexpected mutations
Sharing	Structural sharing saves memory
Caching	Immutable data can be cached

-

Related Topics

• 01 Functional Programming Fundamentals - Pure functions use immutability
• [02 Higher Order Functions & Closures](/05-py3/03-functional-programming/(02-higher-order-functions-closures/) - Closures with immutable data
• [05 Jax & Functional Ml](/05-py3/03-functional-programming/(05-jax-functional-ml/) - JAX's functional approach with immutability
• 00 Readme - Memory efficiency of immutability