Столкнулся с проблемой нормальной реализации коллекций в PHP. Доктриновские коллекции мутабельны и инвариантны. PSL коллекции инвариантны. Нигде не видел непустых коллекций. Везде меня что-то не устраивало и было принято решение написать свою open source реализацию иммутабельных коллекций с ковариантными темплейт-параметрами и выстроенной иерархией пустых и непустых коллекций. В качестве статического анализатора был выбран Psalm.

Иерархия коллекций

Коллекции делятся по возможности содержать пустой список элементов на Collection и NonEmptyCollection.

Получается две иерархии коллекций: обычные коллекции и непустые коллекции.

Обычные коллекции (интерфейс Collection) делятся на интерфейсы Seq, Map и Set.

• Seq - это сокращение от Sequence. Упорядоченный набор элементов с порядковым номером в рамках коллекции. Типичный представитель Seq - это связный список LinkedList.

• Map представляет набор пар ключ-значение. Типичный представитель HashMap.

• Set - это множество уникальных элементов. Типичный представитель HashSet.

Непустые коллекции (интерфейс NonEmptyCollection) делятся на интерфейсы по такому же принципу, как и обычные коллекции, но у них добавляется префикс NonEmpty к соответствующим названиям классов и интерфейсов.

Обычные коллекции

Collection<TV> -> Seq<TV>     -> LinearSeq<TV>   -> LinkedList<TV>
Collection<TV> -> Seq<TV>     -> IndexedSeq<TV>  -> ArrayList<TV>
Collection<TV> -> Set<TV>     -> HashSet<TV>
Collection<TV> -> Map<TK, TV> -> HashMap<TK, TV>

Непустые коллекции

NonEmptyCollection<TV> -> NonEmptySeq<TV> -> NonEmptyLinearSeq<TV>  -> NonEmptyLinkedList<TV>
NonEmptyCollection<TV> -> NonEmptySeq<TV> -> NonEmptyIndexedSeq<TV> -> NonEmptyArrayList<TV>
NonEmptyCollection<TV> -> NonEmptySet<TV> -> NonEmptyHashSet<TV>

Типобезопасность

В библиотеке написаны плагины для статического анализатора Psalm, которые позволяют производить рефайнинг типов элементов и ключей коллекций при выполнении таких операций, как filter и filterNotNull.

<?php

/**
 * Выведенный тип NonEmptyLinkedList<1|2|3>
 */
$collection = NonEmptyLinkedList::collectNonEmpty([1, 2, 3]);

/**
 * Выведенный тип NonEmptyLinkedList<int>
 * 
 * Литеральные типы пропали после трансформации элементов коллекции 
 * Но NonEmpty префикс коллекции сохранился, 
 * Т.к. количество элементов в коллекции не изменилось
 */
$mappedCollection = $collection->map(fn($elem) => $elem - 1);

/**
 * Выведенный тип LinkedList<positive-int>
 * 
 * NonEmpty префикс пропал после фильтрации
 * Т.к. количество элементов могло уменьшиться 
 * И коллекция могла стать пустой 
 */
$filteredCollection = $mappedCollection->filter(fn(int $elem) => $elem > 0);

<?php

/**
 * Выведенный тип non-empty-list<Foo|null|Bar>
 */
$source = [new Foo(1), null, new Bar(2)];

/**
 * Выведенный тип ArrayList<Foo|Bar>
 * 
 * Null был исключен из типа элементов коллекции
 * 
 * NonEmpty префикс коллекции так же пропал после фильтрации
 * Т.к. количество элементов могло уменьшиться 
 * И коллекция могла стать пустой 
 */
$withoutNulls = NonEmptyArrayList::collectNonEmpty($source)->filterNotNull();

/**
 * Выведенный тип ArrayList<Foo>
 * 
 * Bar был исключен из типа элементов коллекции
 */
$onlyFoos = $withoutNulls->filter(fn($elem) => $elem instanceof Foo);

Ковариантность

Тайп-параметры коллекций ковариантны, в отличие от коллекций доктрины и PHP Standart Library (PSL).

<?php

class User {}
class Admin extends User {}

/**
* @param NonEmptyCollection<User> $collection
*/
function acceptUsers(NonEmptyCollection $collection): void {}

/** 
 * @var NonEmptyLinkedList<Admin> $collection 
 */
$collection = NonEmptyLinkedList::collectNonEmpty([new Admin()]);

/**
 * Можно передавать коллекцию админов вместо коллекции пользователей
 * Из-за ковариантности тайп-параметра коллекции
 */
acceptUsers($collection);

Иммутабельность

Коллекции не изменяются после создания. Все мутирующие операции над коллекциями возвращают новые независимые коллекции.

<?php

$originalCollection = LinkedList::collect([1, 2, 3]);

/**
 * $originalCollection не модифицируется
 * И создаётся новая коллекция на основе предыдущей
 */
$prependedCollection = $originalCollection->prepended(0);

/**
 * $prependedCollection не модифицируется
 * И создаётся новая коллекция на основе предыдущей
 */
$mappedCollection = $prependedCollection->map(fn(int $elem) => $elem + 1);

Null-безопасность

Использование монады Option позволяет избежать null pointer исключений. В либе вместо null возвращается всегда либо Some, либо None .

<?php

/**
 * @var Collection<int> $emptyCollection 
 */
$emptyCollection = getEmptyCollection();

/**
 * Операция reduce предполагает работу с непустой коллекцией
 * 
 * Вместо того, чтобы кидать исключение или возвращать null, 
 * если в коллекции нет элементов, 
 * в библиотеке в таких случаях возвращается 
 * экземпляр монады Option<T> (Some<T>|None)
 *
 * Такой подход позволяет получить значение 
 * или продолжить вычисление без проверок на null  
 */
$resultWithDefaultValue = $emptyCollection
    ->reduce(fn(int $accumulator, int $element) => $accumulator + $element)
    ->getOrElse(0);

<?php

class Order
{
    public function __construct(public int $id, public int $price) {}
}

/**
 * In-memory хранилище проиндексированных по ID заказов
 */
$ordersInMemoryStorage = HashMap::collect([
    [$orderId1 = rand(), new Order(id: $orderId1, price: 0)],
    [$orderId2 = rand(), new Order(id: $orderId2, price: 999)],
]);

/**
 * Безопасное деление
 * 
 * Эту операцию можно вставить в качестве промежуточного элемента 
 * цепочки вычислений с помощью метода Option::flatMap
 * 
 * @return Option<float>
 */
function div(int $dividend, int $divisor): Option {
    return 0 === $divisor
        ? Option::none()
        : Option::some($dividend / $divisor);
}

/**
 * Поиск по ключу в Map-коллекции возвращает монаду Option
 * 
 * Это позволяет продолжить описывать цепочку вычислений 
 * с помощью map, flatMap и подобных методов класса Option.
 * 
 * Цепочка вычислений не продолжится, 
 * если элемент не найден в хранилище
 * или если произошло деление на ноль
 * 
 * В случае, если на каком-то этапе вычисления произошла ошибка,
 * то при вызове getOrElse(0) возвратится 0, 
 * вместо успешного результата вычисления
 */
$ordersInMemoryStorage
    ->get($orderId1)
    ->map(fn(Order $order): int => $order->price)
    ->flatMap(fn(int $price): Option => div(1, $price))
    ->getOrElse(0);

Связь HashSet, HashMap и HashContract

HashSet под капотом использует HashMap.

Чем отличается HashMap от обычного массива в PHP? Ключи массивов в PHP могут быть целыми числами или строками. Тип ключей в HashMap ничем не ограничен. Это вполне могут быть экземпляры классов. Numeric-string ключи в массивах PHP преобразуются в целочисленные ключи. В HashMap такого не происходит и элемент с ключем "1" нельзя достать по ключу 1.

HashMap проверяет, не реализует ли объект, который используется в качестве ключа, интерфейс HashContract. Если реализует, то используются реализуемые в классе ключа-объекта методы hashCode и equals, чтобы находить элементы коллекции по ключам.

<?php

/**
 * Если реализовать HashContract (методы hashCode и equals),
 * то можно использовать объекты класса
 * в качестве ключей в HashMap 
 * и в качестве элементов коллекции HashSet
 */
class Foo implements HashContract
{
    public function __construct(public int $a, public bool $b = true)
    {
    }

    /**
     * Сравнивает на равенство текущий объект 
     * с переданным аргументом
     * по типу и значимым полям класса
     *
     * Используется, чтобы находить элементы в бакете 
     * по ключу-объекту данного класса
     */
    public function equals(mixed $rhs): bool
    {
        return $rhs instanceof self
            && $this->a === $rhs->a
            && $this->b === $rhs->b;
    }

    /**
     * Хэш значимых полей класса
     * 
     * Используется, чтобы попадать в нужный бакет 
     * в HashMap'е
     */ 
    public function hashCode(): string
    {
        return md5(implode(',', [$this->a, $this->b]));
    }
}

/**
 * Сборка коллекции происходит с помощью пар ключ-значение,
 * которые передаются в виде массивов вида array{TKey, TValue}
 */
$hashMap = HashMap::collect([
    [new Foo(1), 1], [new Foo(2), 2],
    [new Foo(3), 3], [new Foo(4), 4]
]);

/**
 * Пример использования коллекции HashMap
 * и чейнинга операций над коллекцией
 */
$hashMap
    ->map(fn($elem) => $elem + 1)
    ->filter(fn($elem) => $elem > 2)
    ->reindex(fn($elem, Foo $key) => $key->a)
    ->fold(0, fn(int $acc, array $pair) => $acc + $pair[1]); // 3+4+5=12

/**
 * При сборке коллекции
 * дублирующиеся элементы будут удалены
 * 
 * Останутся только Foo(1), Foo(2), Foo(3), Foo(4)
 */
$hashSet = HashSet::collect([
    new Foo(1), new Foo(2), new Foo(2), 
    new Foo(3), new Foo(3), new Foo(4),
]);

/**
 * Пример использования коллекции HashSet
 * и чейнинга операций над коллекцией
 */
$hashSet
    ->map(fn(Foo $elem) => $elem->a)
    ->filter(fn(int $elem) => $elem > 1)
    ->reduce(fn($acc, $elem) => $acc + $elem)
    ->getOrElse(0); // 9