【Generator】Laravel の LazyCollection を作ってみよう

はじめに

先日， Qiita Night 〜PHP〜 という LT で登壇させていただきました．
僕の発表を聞いてくださった皆様，ありがとうございました！

アーカイブもあるようなので，見逃してしまった方もぜひご覧ください！
また，登壇資料も公開していますので合わせてご覧ください！

内容のおさらい

さて， LT の前半では主に PHP におけるイテレータの話をしました．
PHP には反復可能であることを保証する型として iterable というものがあります．この型は実際には array|Traversable の型エイリアスです．
さらに， Traversable は Iterator と IteratorAggregate に分かれ．．．というふうに，イテレータの話も深ぼっていけばかなりの量になります笑
LT は 7 分という短い時間でしたのであまり深ぼることはできませんでしたが， PHP の反復処理については以下の記事がとても簡潔にまとめてあって僕も参考にさせていただきましたので是非読んでみてください．

そして後半では，ジェネレータの紹介をしました．
Generator は，特別な文法を持つ関数（ジェネレータ関数）から自動定義される， Iterator を実装したクラスです．
Generator の良さは大きく2点あって，

• 簡単に Iterator の実装を定義できる
• 遅延評価されるので省メモリ

です．
LT でも話しましたが， Generator を作る場合，反復処理で値を生成してほしいところで yield を記述します．yield が 1 個以上書かれた関数はジェネレータ関数となり，ジェネレータ関数を実行して得られる Generator は Iterator として使うことができます．
また， Generator が反復処理で生成する値はループ1回ごとに遅延評価で作られていくため，理論上無限長のリストを扱うことができます．これは複数種類のループ処理を連結するときに大きな力を発揮します．

具体的には，配列であれば 『1種類目の処理を要素全てに適用，その結果として集めた要素の配列を2種類目の処理に渡して要素全てに適用，…』 となるところを 『1要素目に処理全てを順に適用，2要素目に処理全てを順に適用，…』 のように，適用順序を転置させることができます。
これによって 「処理が完了した要素が必要な数だけ集まったらループを中断」 や 「ある要素の処理が完了したらメモリからそれを破棄し，次の要素の処理を開始する」 といった，もし配列であれば要素数に比例して大量のメモリを消費してしまうロジックを，要素数に依存せず極めて省メモリで実現できる特性を持っています．

LT では以下のような例を示しながら，大量のデータを愚直に配列で直列にフィルターする場合と，Generator を使う場合で処理の順番にどのような違いがあるのかを見ていきました．

<?php
// CSV などからデータを読み込む(今回は [6, 2, 10, 9, 3, 12] という自然数列)
$data = read_data();

// 5 以上の整数に絞る
$result = filter_1();

// 偶数に絞る
$result = filter_2();

// 先頭から 2 件取得
$result = take($result, 2);

foreach ($result as $item) {
    echo "$item を出力します";
}

今日の本題

さて，先の LT では PHP の Iterator や Generator の基礎的なお話をしました．
本記事では，実際に Generator を使って普段の開発を便利にするライブラリを作ってみましょう！

Laravel には Collection という配列操作用便利ライブラリがあります．配列データを内包させることで， iterable なオブジェクトとして扱い， map() や filter() など， JavaScript の Array.prototype や Rust の Iter のようにメソッドチェーンで配列を操作することができます（実際には配列だけではなく Enumerable， Arrayable, Traversable, Jsonable, JsonSerializable, UnitEnum であれば内包することができます）．

また， Laravel にはこの遅延評価版の LazyCollection というものがあります．
これは， Collection と同じ Illuminate\Support\Enumerable インタフェースを実装しているため，Collection で使えるデータ操作メソッドはそのまま使えた上で，内部的には Generator を使いデータの全てをメモリに乗せないようにしたものです．
EloquentModel からも lazy() メソッドを使うことができ， DB から受け取る結果を LazyCollection として取得できます．

lazy() メソッドは実際は Illuminate\database\Query\Builder::class から使うことができますが，実装の実体は Illuminate\database\Concerns\BuildsQueries トレイトに定義されています． 興味のある方は是非見てみてください．

https://github.com/illuminate/database/blob/master/Concerns/BuildsQueries.php

LazyCollection は便利ですが Laravel 以外のプロジェクトでの導入は大変です．

実装を見てみると以下の3つに依存していますので単にコピペするだけでは難しいですし，

use Illuminate\Contracts\Support\CanBeEscapedWhenCastToString;
use Illuminate\Support\Traits\EnumeratesValues;
use Illuminate\Support\Traits\Macroable;

illuminate/collections を Composer で入れても良いのですが要らないものもくっついてきますのであんまりオススメできません．（そもそも Laravel でないプロジェクトならば Illuminate を入れたくないですよね）

もしかしたら良いライブラリが見つかるかもしれませんが，せっかく Generator を勉強したのでちょっと作ってみましょう！

LazyCollection を作ってみよう

本記事で全ての機能を網羅するのは流石に大変ですのでよく使いそうなメソッドをいくつかピックアップします．

• make() ・・・ 新しい LazyCollection インスタンスを生成する静的メソッド
• map() ・・・ コレクションの各値に指定したコールバックを当てた結果を，新しい LazyCollection に詰めて返す
• each() ・・・ コレクションの各値に指定したコールバックを当てる
• filter() ・・・ 指定したコールバックでコレクションをフィルタリングする
• take() ・・・ 指定したアイテム数の新しい LazyCollection を生成する
• unique() ・・・ コレクションのアイテムから重複を取り除く
• union() ・・・ 2つの LazyCollection を結合する

さらに，今回は実装難易度を下げるために以下の制約を設けます．

• 一次元
• キーは持たない

ただし，本家との差別化を図りたいため，全てのメソッドが無限長リストを想定した実装になるようにしたいと思います．
じつは， Laravel の LazyCollection ではメソッドによってはその機能の性質上無限長のリストを扱うことができないものがあります．
例えば， 全ての要素を取り出して配列に変換する all() は，内部的には iterator_to_array() が使われていますが，仮に無限長リストを iterator_to_array() に渡した場合， Generator は値を生成し続けるため無限ループしてしまいます．
そのため，無限長の Generator/Iterator でハングしてしまう機能は安全のため実装しないことにします．
今回実装する LazyCollection については，もし扱うデータが有限長であると利用者側で判断できる場合は，自己責任で iterator_to_array あるいは [...$iter] などを書いていただければいいと思います.

下準備

LazyCollection インスタンス自体が反復可能な値になる必要があるため，反復可能であることを保証する何らかのクラスを継承するか，そのようなインタフェースを実装する必要があります．

• Generator::class ・・・ そもそも final class なので継承不可
• Traversable インタフェース ・・・ 内部的な型なので実装不可
• Iterator インタフェース ・・・ 候補の一つ．ただし次の 5 つのメソッドを実装する必要がある
  • current()
  • key()
  • next()
  • rewind()
  • valid()
• IteratorAggregate インタフェース ・・・ 候補の一つ． getIterator() を実装するだけで良い

ということで，今回は IteratorAggregate インタフェースを使ってみようと思います．

<?php

declare(strict_types=1);

use Closure;
use Generator;
use InvalidArgumentException;
use IteratorAggregate;

class LazyCollection implements IteratorAggregate
{
    public function __construct(
        private readonly iterable|Closure $items,
    ) {
        if ($this->items instanceof Generator) {
            throw new InvalidArgumentException('Generator は渡せません');
        }
        if ($this->items instanceof Closure && !($this->items)() instanceof Generator) {
            throw new InvalidArgumentException('ジェネレータ関数を渡してください');
        }
    }

    public function getIterator(): Generator
    {
        if ($this->items instanceof Closure) {
            yield from ($this->items)();
        } else {
            yield from $this->items;
        }
    }
}

コンストラクタが少しイメージと違うかもしれません．これは，Laravel の LazyCollection も同様な実装になっていますが，ポイントは iterable なものかジェネレーター関数を受け取るが Generator は受け取れない という点です．
iterable なものを受け取れるのは直感的ですが， Generator を受け取ると少々不都合があるため，代わりにジェネレータ関数を受け取れるようにしています．
もし仮に Generator を受け取った場合， 一度 getIterator() で全ての値を生成し読みきったあとに再度 getIterator() を呼ぶとどうなるでしょうか？答えは 何も返ってこない です．
先の LT でも少し触れましたが， Generator は値を 消費 します．つまり生成して使われたあとはその値は捨てられることになります． Generator 自体に自身を再生成する機能や，読み込んだ値を保持しておく機能はないため，一度読み取られきった Generator はもう値を生成することはありません．
対して，ジェネレータ関数であれば，実行すれば都度 Generator を生成するため， Generator 以外の Iterator で言うところの rewind() 的なことが実現できるわけです．（ただし， rwwind() がカーソルを先頭に戻すのに対し， Generator の再実行は新しい Generator が出来ているという点で，厳密に等価な処理ではないことに注意してください．）

getIterator() では， ジェネレータ関数だった場合は関数を実行して Generator を生成し return, そうでなければ， iterable なものですので，要素を順番に yield します．
また， 以下のような記法は，

yield from $this->items;

foreach ($this->items as $item) {
    yield $item;
}

をシンプルに表現したものです．
これはジェネレータの委譲と呼ばれるもので，他の iterable なもの（Traversable オブジェクトまたは配列）の各値を yield したい場合に簡潔に書くことができて便利です．

なお， 「ジェネレータ関数または iterable かどうか」のような制約はは， PHPDoc で型を定義しておくと静的解析できるのでオススメです．

make()

このメソッドは， LazyCollection::make($items); のような使い方をするもので， iterable な何か（もしくはジェネレータ関数）を LazyCollection でラップする際に使うものです．

public static function make(iterable|Closure $items): static
{
    return new static($items);
}

make() は簡単です．受け取ったものをそのまま自分に詰めて新しいインスタンスとして返してあげるだけです．
これは本家の LazyCollection と全く同じ実装です．

map()

このメソッドはコールバックを引数に受け取り，コレクションの各要素に対してコールバックを適用した上で，その結果を新しい LazyCollection に詰め直して返すものです．

public function map(callable $callback): static
{
    return new static(function () use ($callback): Generator {
        foreach ($this->getIterator() as $item) {
            yield $callback($item);
        }
    });
}

もちろんですが， foreach の中ではコールバックの結果を yield する必要があります．
まt，コンストラクタはジェネレータ関数を受け取ることができるため，クロージャを直接書いてあげれば良いです．

each()

このメソッドは map() と近いですが，大きな違いはコールバックが返した値は読み捨てられるという点で，返り値は $this となります．

Tips
実は， Larael の LazyCollection においては， each() はチェーンされた処理をすべて評価して終端させることを意味します．
Collection の場合はここの返り値の $this （自分自身）から再度別の処理に繋ぐこともできました． LazyCollection においても表面上同じ振る舞いをしますが，内部的には全要素の正格評価という作用を起こすため，注意してください．終端を目的とせず，さらに後ろに続く処理のために遅延させたいのであれば，代わりに tapEach() を使用します.

今回は， Laravel の LazyCollection::tapEach() 相当のものを each() として実装します．

public function each(callable $callback): static
{
    return new static(function () use ($callback): Generator {
        foreach ($this->getIterator() as $item) {
            if ($callback($item) === false) {
                break;
            }
            yield $item;
        }
    });
}

基本的には map() の実装と同じですが， yield するものが $callback() から $item に変わったのと， コールバックの結果が false であればそこでループが終了するという点が異なります．

filter()

このメソッドは指定したコールバックでコレクションをフィルタリングするというものです． コールバックが true を返した場合にアイテムが残ります． Laravel では，コールバックに何も渡さなかった場合は, falsy なアイテムを削除します．

public function filter(callable $callback = null): static
{
    if (is_null($callback)) {
        $callback = function ($value) {
            return (bool) $value;
        };
    }

    return new static(function () use ($callback): Generator {
        foreach ($this->getIterator() as $item) {
            if ($callback($item)) {
                yield $item;
            }
        }
    });
}

こちらも本家とほとんど同じコードです．
コールバックが渡されなかった場合に (bool)$value を返すクロージャをセットするという前処理が非常にスッキリしていて良いですね．
実際のフィルター部分は，コールバックが true を返せばその時の値をそのまま yiled するし，そうでなければそのままスキップするという実装になっています．

take()

このメソッドは指定したアイテム数の新しい LazyCollection を生成するというもので，要は欲しい数だけ頭から要素を取得できるメソッドになります．
Laravel では， 引数が正のときコレクションの先頭から値を取得し，引数が負のときコレクションの最後から取得するようになっていますが， Generator の性質上逆順を扱うことはできないため，一旦普通の Collection に変換する必要があります．しかし，今回のように無限長リストを扱う可能性を想定しているのなら，一旦 Collection に変換することができないので， $limit が 0 以下の場合は空の LazyCollection を返すという仕様にすることにしましょう．

public function take(int $limit): static
{
    if ($limit <= 0) {
        return new static([]);
    }

    return new static(function () use ($limit): Generator {
        $iterator = $this->getIterator();
        while ($limit--) {
            if (! $iterator->valid()) {
                break;
            }

            yield $iterator->current();

            if ($limit) {
                $iterator->next();
            }
        }
    });
}

ロジックとしては今までで一番複雑だったのではないでしょうか．ここでは Generator が Iterator であると感じられる部分も見受けられますね．
$item が 0 以下であれば return new static() に空配列渡すようにしています．
while の中では $limit をデクリメントしながら，値があれば返してカーソルを進める，値がなければ終わり，というような処理を反復しています． 今回使用した Iterator のメソッドは次のような機能があります．

• valid() ・・・ 現在位置が有効かどうかを bool で返す
• current() ・・・ 現在位置の値を返す
• next() ・・・ カーソルを進める（次の要素に進む）

unique()

このメソッドはコレクションのアイテムから重複を取り除きます．
Laravel の Collection でこのメソッドのシグネチャは unique($key=null, $strict=false): static となっていて，第 1 引数の $key は Collection がネストしている配列を内包していた場合，どの key に対応する値をユニークにするかを決めることができ，第 2 引数 の $strict は厳格な比較を行うかどうかを決める bool 値です．
今回の仕様では，ネストしたデータは扱わないので第 1 引数は必要なく，（これは好みですが）常に厳格な比較を行いたいため第 2 引数で厳格比較をオプショナルにする必要もありません．

public function unique(): static
{
    return new static(function (): Generator {
        $exists = [];

        foreach ($this->getIterator() as $item) {
            if (!in_array($item, $exists, true)) {
                yield $item;

                $exists[] = $item;
            }
        }
    });
}

$exists という配列にすでに存在するものを記憶しておいて， 要素が $exists に含まれていない場合にその値を取り出すというものです．
実装していて気づいたのですが， $exists の要素は当然全部メモリに乗るため，無限長リストを扱う場合 $exists がメモリに乗り切らない可能性があるなと思いました．
よって，厳密に無限長リストを許容する LazyCollection を実装するならば unique() の実装は理論上不可能なようです．

union()

このメソッドは渡されたアイテムを自身に結合させるというものです． 配列だと + で結合できますが， Iterator はできませんので明示的に処理を書く必要があります．

public function union(iterable $items): static
{
    return new static(function () use ($items) : Generator {
        foreach ($this->getIterator() as $item) {
            yield $item;
        }
        foreach ($items as $item) {
            yield $item;
        }
    });
}

なぜ yield from を使わないのか？と疑問に思われた方もいらっしゃるかもしれません．
一見 yield from を使って書けそうな処理ですが， foreach を使ったのにはちゃんとした理由があります．
今回，記事の前半で実装簡単化のために キーを持たない というふうにルールを決めました．今回のように明示的にキーを持たない場合，Generator は内部的に整数の連番のキーを持っています．また， yield from はキーをリセットしません． yield from に渡された iterable のキーをそのまま利用します．つまり，今回のように続けて yield from を書いた場合，キーが重複した際は後から来た値がそれまでの値を上書きするのです．
したがって，今回の要件だと意図した動作にならない可能性がありますので，あえて yield from は使わす foreach でそれぞれ順番に yield することにしました．

実装をまとめてみる

まとめてみるとこんな感じです．

LazyCollection.php

<?php

declare(strict_types=1);

namespace App\Generators;

use Closure;
use Generator;
use InvalidArgumentException;
use IteratorAggregate;

class LazyCollection implements IteratorAggregate
{
    public function __construct(
        private readonly iterable|Closure $items,
    ) {
        if ($this->items instanceof Generator) {
            throw new InvalidArgumentException('Generator は渡せません');
        }
        if ($this->items instanceof Closure && !($this->items)() instanceof Generator) {
            throw new InvalidArgumentException('ジェネレータ関数を渡してください');
        }
    }

    public function getIterator(): Generator
    {
        if ($this->items instanceof Closure) {
            yield from ($this->items)();
        } else {
            yield from $this->items;
        }
    }

    public static function make(iterable|Closure $items): static
    {
        return new static($items);
    }

    public function map(callable $callback): static
    {
        return new static(function () use ($callback): Generator {
            foreach ($this->getIterator() as $item) {
                yield $callback($item);
            }
        });
    }

    public function each(callable $callback): static
    {
        return new static(function () use ($callback): Generator {
            foreach ($this->getIterator() as $item) {
                if ($callback($item) === false) {
                    break;
                }
                yield $item;
            }
        });
    }

    public function filter(callable $callback = null): static
    {
        if (is_null($callback)) {
            $callback = function ($value) {
                return (bool) $value;
            };
        }

        return new static(function () use ($callback): Generator {
            foreach ($this->getIterator() as $item) {
                if ($callback($item)) {
                    yield $item;
                }
            }
        });
    }

    public function take(int $limit): static
    {
        if ($limit <= 0) {
            return new static([]);
        }

        return new static(function () use ($limit): Generator {
            $iterator = $this->getIterator();
            while ($limit--) {
                if (! $iterator->valid()) {
                    break;
                }

                yield $iterator->current();

                if ($limit) {
                    $iterator->next();
                }
            }
        });
    }

    public function unique(): static
    {
        return new static(function (): Generator {
            $exists = [];

            foreach ($this->getIterator() as $item) {
                if (!in_array($item, $exists, true)) {
                    yield $item;

                    $exists[] = $item;
                }
            }
        });
    }

    public function union(iterable $items): static
    {
        return new static(function () use ($items) : Generator {
            foreach ($this->getIterator() as $item) {
                yield $item;
            }
            foreach ($items as $item) {
                yield $item;
            }
        });
    }
}

まとめ

Generator はいいぞ！

宣伝

Rust にもイテレータがあるという話を本記事中にほんの少し触れましたが， Rust のイテレータに実装されている関数をそのまま PHP のイテレータで使えるようにした phpiter というライブラリを同期のしけちゃんが作っていました．
もちろん Generator を渡せば遅延評価できるようになっていますので，是非使ってみてください！