Skip to content

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: all trees share the root node
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