Persistent Data Structures in PHP: Functional Lists with Structural Sharing

1. What sets persistent data structures apart from plain array copies

A persistent data structure is a data structure that keeps its previous version fully unchanged after every modification operation and returns a new version instead. The term persistent here does not refer to disk storage, but to all earlier versions continuing to exist in memory. Anyone holding a reference to the old version continues to see exactly the original state even after a change to the new version, because both versions exist side by side.

The naive way to achieve this behavior in PHP would be to copy the entire array on every change. PHP arrays do use copy-on-write internally, which makes simple assignments cheap, but as soon as an element is actually modified, added, or removed, PHP copies the entire internal array storage before applying the change. For large lists with frequent changes, this copy overhead quickly becomes a performance problem.

Persistent data structures in the functional sense solve this problem through structural sharing: a new version shares as much internal storage as possible with the old version and only copies the strictly necessary part. This article shows what such a persistent linked list looks like in PHP 8.4 and when it is actually superior to classic arrays.

2. The copying problem of classic PHP arrays under immutability

If you want to treat an array as immutable in PHP, the obvious approach is to create a copy on every change via $newArray = $oldArray; $newArray[] = $element;. For small arrays this is unproblematic, because PHP's copy-on-write mechanism only triggers the actual copy on the first write access to the copy, and this copying barely registers for a small number of elements.

For large arrays with thousands of elements and frequent changes, such as an undo history that needs a new, immutable version of the state at every step, the copying overhead adds up noticeably. Every single change copies the entire array again, with quadratic total complexity for a chain of n changes on an array with n elements. Persistent data structures avoid exactly this quadratic behavior through shared, unchanged storage between versions.

<?php

declare(strict_types=1);

// Naive immutability: full array copy on every change
function prependNaive(array $list, mixed $item): array
{
    // PHP copies the entire internal array storage here on write
    array_unshift($list, $item);

    return $list;
}

$history = [];
for ($i = 0; $i < 3; $i++) {
    $history[] = $list ?? [];
    $list = prependNaive($list ?? [], $i);
}

// Each step in $history is a full, independent copy — costly at scale
foreach ($history as $step) {
    echo count($step) . ' elements in this version' . PHP_EOL;
}

3. An immutable linked list as the base building block

The classic building block for persistent data structures is the singly-linked list, where each node holds a value and a reference to the rest of the list. In PHP such a node can be modeled as an immutable value object with readonly properties: a value and a reference to the next node, or null for the end of the list.

The decisive difference from a PHP array: the list itself is made of immutable nodes that are never modified again after creation. Every operation that produces a new list therefore does not need to copy existing nodes, it can simply reuse them and only create the actually new nodes. This property is the foundation for structural sharing in the next section.

<?php

declare(strict_types=1);

/**
 * An immutable singly-linked list node. Once created, never mutated.
 *
 * @template T
 */
final class ListNode
{
    /**
     * @param T $value
     * @param self<T>|null $next
     */
    public function __construct(
        public readonly mixed $value,
        public readonly ?self $next,
    ) {
    }
}

/**
 * A persistent, immutable list wrapper around a linked chain of nodes.
 *
 * @template T
 */
final class PersistentList
{
    private function __construct(private readonly ?ListNode $head)
    {
    }

    /**
     * @return self<mixed>
     */
    public static function empty(): self
    {
        return new self(null);
    }

    public function isEmpty(): bool
    {
        return $this->head === null;
    }
}

4. Structural sharing: why prepend() needs no copy

Prepending a new element to a persistent data structure is the cheapest of all operations, because it only requires creating a single new node that points to the previous head of the old list. The old list remains fully reachable and unchanged, because its head node continues to exist and is never modified by anyone. This technique is called structural sharing: the new version shares the entire remaining storage with the old version and only duplicates the one new node.

The runtime cost of prepend is therefore constant regardless of list size, O(1), while a naive array copy via array_unshift on an immutable copy always has to touch the entire dataset, O(n). For frequent prepend operations on large histories, such as building an event log from newest to oldest, this difference is clearly noticeable in practice.

<?php

declare(strict_types=1);

/**
 * @template T
 */
final class PersistentList
{
    private function __construct(private readonly ?ListNode $head)
    {
    }

    /**
     * @return self<mixed>
     */
    public static function empty(): self
    {
        return new self(null);
    }

    /**
     * O(1): only one new node is allocated, the old list is fully reused.
     *
     * @param T $value
     * @return self<T>
     */
    public function prepend(mixed $value): self
    {
        return new self(new ListNode($value, $this->head));
    }

    /**
     * @return list<mixed>
     */
    public function toArray(): array
    {
        $items = [];
        $node = $this->head;

        while ($node !== null) {
            $items[] = $node->value;
            $node = $node->next;
        }

        return $items;
    }
}

$v1 = PersistentList::empty();
$v2 = $v1->prepend('a');
$v3 = $v2->prepend('b');

// $v2 remains fully intact and unaffected by the creation of $v3
var_dump($v2->toArray()); // ['a']
var_dump($v3->toArray()); // ['b', 'a']

5. Functional operations: map, filter and fold on the list

For a persistent data structure to become practically useful, it needs the same functional operations known from arrays: map to transform every element, filter to keep only certain elements, and fold to reduce to a single value. All three operations produce a new, immutable list or a single value, without ever changing the original list, consistent with the core principle of immutability.

When implementing map and filter on a linked list, one must consider that a naive recursive implementation can blow the stack for very long lists, because every recursive call consumes a new stack frame. An iterative implementation with an explicit loop avoids this risk and stays safe for lists of any length.

<?php

declare(strict_types=1);

/**
 * @template T
 */
final class PersistentList
{
    private function __construct(private readonly ?ListNode $head)
    {
    }

    /**
     * @return self<mixed>
     */
    public static function empty(): self
    {
        return new self(null);
    }

    /**
     * @param T $value
     * @return self<T>
     */
    public function prepend(mixed $value): self
    {
        return new self(new ListNode($value, $this->head));
    }

    /**
     * Iterative map — avoids stack overflow on very long lists.
     *
     * @param Closure(mixed): mixed $fn
     * @return self<mixed>
     */
    public function map(Closure $fn): self
    {
        $items = array_map($fn, $this->toArray());
        $result = self::empty();

        foreach (array_reverse($items) as $item) {
            $result = $result->prepend($item);
        }

        return $result;
    }

    /**
     * @param Closure(mixed): bool $predicate
     * @return self<mixed>
     */
    public function filter(Closure $predicate): self
    {
        $items = array_filter($this->toArray(), $predicate);
        $result = self::empty();

        foreach (array_reverse($items) as $item) {
            $result = $result->prepend($item);
        }

        return $result;
    }

    /**
     * @return list<mixed>
     */
    public function toArray(): array
    {
        $items = [];
        $node = $this->head;

        while ($node !== null) {
            $items[] = $node->value;
            $node = $node->next;
        }

        return $items;
    }
}

$numbers = PersistentList::empty()->prepend(3)->prepend(2)->prepend(1);

$doubled = $numbers->map(fn (int $n): int => $n * 2);
$evens = $numbers->filter(fn (int $n): bool => $n % 2 === 0);

var_dump($numbers->toArray()); // [1, 2, 3], unaffected by map/filter above
var_dump($doubled->toArray()); // [2, 4, 6]

6. The append problem: why append() stays more expensive than prepend()

While prepend on a singly-linked list works in constant time, appending an element to the end of the list, append, is structurally more expensive. To attach a new node at the end without changing existing nodes, every node along the way to the end would need to be newly created, because each immutable node points to its successor, and that successor would change through the append. This makes append cost O(n) instead of O(1) on this simple structure.

Real functional languages and libraries solve this problem with more advanced structures such as balanced trees or finger trees, which allow both prepend and append in amortized constant or logarithmic time. For most practical PHP use cases, where insertion mostly happens at the front or a complete new iteration is done, the simple linked list with its O(n) append is entirely sufficient, as long as append is not the dominant use case.

7. Real-world cases: undo history and shared state without copies

An obvious use case for persistent data structures is an undo history in an interactive application: every user action produces a new version of the state, while all previous versions remain unchanged in memory and can be reactivated instantly if needed. With a naive array copy on every action, a long undo chain over a large state would quickly consume excessive memory, because every version duplicates the entire state.

A second use case concerns concurrent or parallel code, for example in a Swoole worker with multiple coroutines: if several coroutines share a reference to the same persistent data structure, none of them can accidentally change the state seen by another, because every change always returns a new version instead of mutating the shared structure. This property makes persistent structures inherently safe against race conditions on the data state itself.

8. Limits: memory overhead and when classic arrays fit better

The price for structural sharing is a higher memory overhead per element compared to a classic PHP array, because each node is its own object with a reference to the next node, instead of sitting in a contiguous block of memory. For very large datasets that are rarely modified and mostly just read, a classic array with its more compact storage and faster sequential access is often the better choice.

Random access to an element by index is also structurally slower for a linked list, O(n) instead of O(1) as with an array, because one must walk node by node from the head. Persistent data structures therefore pay off specifically where immutability, many versions, and shared state matter more than fast index access, not as a generic replacement for every PHP array.

9. Persistent list compared to array and SplDoublyLinkedList

The following table compares the persistent list with the common alternatives in PHP.

The rule of thumb: a persistent list pays off as soon as multiple versions of a state must stay alive at the same time, such as with undo histories or shared state between coroutines. For pure sequential data traversal without a versioning need, the classic PHP array remains the better choice most of the time, thanks to its lower memory overhead and faster index access.

10. Summary

Persistent data structures keep their previous version fully unchanged after every modification and produce a new version through structural sharing instead of a full copy. An immutable, singly-linked list with readonly nodes makes prepend() possible in constant time, because only a single new node is created and the rest of the old list is reused unchanged. Functional operations such as map, filter and fold can be implemented on this structure without ever changing the original list.

The price is a higher memory overhead per element and slower index access compared to a classic array. Persistent data structures therefore pay off specifically for undo histories, version management and shared state between concurrent code, not as a generic replacement for every PHP array in everyday code.

11. FAQ: Persistent Data Structures in PHP