A concept for lazy collections using copy-on-write (I think)

copy_on_write_lazy_map.php

<?php

interface Collection
{
    /**
     * @return static
     */
    function map(callable cb): Collection;
    // filter
    // reduce
    // any
    // all
    // ...
}


/**
 * An iterator that yields values modified by a callback, preserving keys.
 */
class MapIterator implements IteratorAggregate
{
    private $collection;
    private $callback;

    public function __construct(Collection $collection, callable $callback)
    {
        $this->collection = $collection;
        $this->callback   = $callback;
    }

    public function getIterator()
    {
        foreach ($this->collection as $key => $value) {
            yield $key => $this->callback($value);
        }
    }
}


/**
 * An iterator that yields no values.
 */
class EmptyIterator implements IteratorAggregate
{
    public function getIterator()
    {
        yield from [];
    }
}


/**
 * A collection that is backed by an iterator which is only evaluated as needed.
 */
abstract class LazyCollection implements IteratorAggregate, Collection
{
    protected $iter;

    public function __construct(Iterator $iter = null)
    {
        $this->iter = $iter ?? (new EmptyIterator);
    }

    /**
     * Evaluates the remaining values in the iterator.
     *
     * @todo What happens when we rewind the iterator?
     * @todo When we clone $this, what happens to the iterator?
     */
    abstract protected function evaluate(): Iterator;

    /**
     * Create a copy if referenced more than once, otherwise return self.
     */
    protected function copyOnWrite()
    {
        return (internal_refcount_func($this) > 1) ? clone $this : $this;
    }

    /**
     * Generates a new collection from this collection keys and mapped values.
     *
     * @return static
     */
    public function map(callable $cb): Collection
    {
        /* External */
        $MapIterator = function (Collection $c) {
            foreach ($collection as $index => $value) {
                yield $index => cb($value);
            }
        };

        return new static(new MapIterator($this));
    }
}


/**
 * Basic list, but lazy.
 */
final class LazyList extends LazyCollection
{
    /**
     * Internal storage.
     */
    private $data = [];

    /**
     * Evaluates the remaining values in the iterator.
     */
    protected function evaluate(): Iterator
    {
        for ($iter = $this->iter; $iter->valid(); $iter->next()) {
            $value = $iter->current();

            /* Add to the cache. */
            $this->data[] = $value;

            yield $value;
        }
    }

    /**
     * Appends a single value and returns the resulting Sequence, which could
     * either be this instance or a clone.
     */
    public function push($value): Sequence
    {
        $result = $this->copyOnWrite();

        $result->data[] = $value;

        return $result;
    }

    /**
     * Yield from cached data first, then from the iterator, caching as we go.
     */
    public function getIterator()
    {
        $index = 0;

        foreach ($this->data as $value) {
            yield $index++ => $value;
        }

        /* TODO: What happens when we rewind the iterator? */
        foreach ($this->evaluate() as $value) {
            yield $index++ => $value;
        }
    }
}


/**
 * Basic set of distinct values.
 */
final class LazySet extends LazyCollection
{
    /**
     * Internal storage.
     */
    private $data = [];

    /**
     * Evaluates the remaining values in the iterator.
     */
    protected function evaluate(): Iterator
    {
        for ($iter = $this->iter; $iter->valid(); $iter->next()) {
            $value = $iter->current();

            /* Do not include the value if already cached. */
            if (isset($this->data[$value])) {
                continue;
            }

            /* Add to the cache. */
            $this->data[$value] = true;

            yield $value;
        }
    }

    /**
     * Adds a value to this Set if the value is not already in this Set.
     */
    public function add($value): Sequence
    {
        /* Do not do anything at all if the operation has no effect. */
        if (isset($this->data[$value])) {
            return $this;
        }

        /* Evaluate the remaining values in the iterator */
        foreach ($this->evaluate() as $candidate) {
            if ($value === $candidate) {
                return $this;
            }
        }

        /* We are about to make an update, so check if we need to copy first. */
        $result = $this->copyOnWrite();

        /* Add the value to the set. */
        $result->data[$value] = true;

        return $result;
    }

    /**
     * Determines if this Set contains the given value.
     */
    public function has($value): bool
    {
        if (isset($this->data[$value])) {
            return true;
        }

        /* Evaluate the remaining values in the iterator */
        foreach ($this->evaluate() as $candidate) {
            if ($value === $candidate) {
                return true;
            }
        }

        return false;
    }

    /**
     * Iterator using a sequential index of the data store's keys as values.
     */
    public function getIterator()
    {
        $index = 0;

        foreach ($this->data as $value => $_) {
            yield $index++ => $value;
        }

        foreach ($this->evaluate() as $value) {
            yield $index++ => $value;
        }
    }
}