PHPで無限ストリームの直積(まとめ)

配列同士の直積、つまりそれぞれの配列から要素を1つずつ選ぶ全ての組み合わせを取得する処理を、無限ストリームに拡張できないかと考え、PHPで任意個のiterableの直積という形でそれを実装した。

振り返り

検証的にはPHPで無限ストリームの直積(3) - terazzoの日記で一旦完成であとは蛇足ですね。コードもこの段階のものが一番本質的だと思う。

記事一覧

  1. PHPで無限ストリームの直積(1) - terazzoの日記
    • 無限ストリームの2個の直積を生成するHaskellのサンプルを参考にPHPで実装した
    • その際、生成済みの値を含めて段階的に値を生成するgradual_iteratorの概念を導入した
    • また、「対角線」ではなく「L字型」で生成するパターンも検討した
  2. PHPで無限ストリームの直積(2) - terazzoの日記
    • 1のコードを元に無限ストリームの3個の直積を実装した
    • その際、各Iteratorを「次元」、出力済みの値のリストを「辺」、新規の値を「点」とみなすメタファーを導入した
  3. 閑話休題 - terazzoの日記
    • 複数配列(つまり有限の)の直積を求めるコードを実装した
  4. PHPで無限ストリームの直積(3) - terazzoの日記
    • 2のコードを元に4個以上(個数を制限しない)の無限ストリームの直積を実装した
    • 『各「次元」から「辺」もしくは「点を」選択する処理』および『各次元の「辺」「点」から全ての値を生成する処理』がどちらも「複数配列の直積」で表せることが分かった
  5. PHPで無限ストリームの直積(4) - terazzoの日記
    • 4のコードを元に有限の配列を混在させても動くようにした
  6. PHPで無限ストリームの直積(5) - terazzoの日記
    • 5のコードを最適化し、あまりメモリを消費しないようにした

実装

なんでこんなコードになってるのっていうのは過去のエントリを読めば理解できると思う。

/** 複数のiterableの直積をIteratorで戻す*/
function iterator_cartesian_product(iterable ...$iterators): \Iterator
{
    foreach (gradual_iterator_zip(...$iterators) as $dimensions) {
        foreach (configure($dimensions) as [$edge_only, $configuration]) {
            if (!$edge_only) {
                yield from array_cartesian_product_iterator(...$configuration);
            }
        }
    }
}

/** 配列の直積を生成するIteratorを戻す */
function array_cartesian_product_iterator(array ...$arrs): \Iterator
{
    if (empty($arrs)) {
        yield [];
        return;
    }
    $array = array_shift($arrs);
    if (!empty($array)) {
        foreach (array_cartesian_product_iterator(...$arrs) as $values) {
            foreach ($array as $value) {
                yield [$value, ...$values];
            }
        }
    }
}
/**
 * 複数のiterableをgradual_iterator化した上でzipする。
 * 全てのiterableの値が尽きたら終了する。
 */
function gradual_iterator_zip(iterable ...$iters): \Iterator
{
    $gradual_iterators = array_map(gradual_iterator(...), $iters);
    while (true) {
        $any_valid = false;
        $values = [];
        foreach ($gradual_iterators as $iter) {
            [$cached, $last, $valid] = $iter->current();
            $iter->next();
            $any_valid = $any_valid || $valid;
            $values[] = [$cached, $last];
        }
        if (!$any_valid) {
            return;
        }
        yield $values;
    }
}
/**
 * iterableから段階的に値を出すIteratorを作る。
 * Iteratorは[生成済みの値の配列, [新規に生成した値], 新規の値の有無]を生成する。
 * 元のiterableの値が尽きても値を生成し続ける。
 */
function gradual_iterator(iterable $iter): \Iterator
{
    $cached = [];
    foreach ($iter as $last) {
        yield [$cached, [$last], true];
        $cached[] = $last;
    }
    // 値が尽きても出し続ける(validかどうかは戻り値で渡す)
    while (true) {
        yield [$cached, [], false];
    }
}
/**
 * それぞれが配列である2要素の配列の配列から、
 * どちらかの要素を取った組み合わせを生成するIteratorを戻す。
 * 但し、要素が空配列の場合はスキップする。
 * 戻されたIteratorは[全てが1要素目かどうか, 組み合わせの配列]を生成する。
 */
function configure(array $dims): \Iterator
{
    if (empty($dims)) {
        yield [true, []];
        return;
    }
    [$edge, $point] = array_shift($dims);

    foreach (configure($dims) as [$edge_only, $confs]) {
        if (!empty($edge)) {
            yield [$edge_only, [$edge, ...$confs]];
        }
        if (!empty($point)) {
            yield [false, [$point, ...$confs]];
        }
    }
}

使用例

test(
    'yields cartesian product of 4 itarables',
    function () {
        $iterator = iterator_cartesian_product(
            sequence(0),
            range('a', 'z'),
            range('A', 'Z'),
            range('!', '/'),
        );
        $result = iterator_take($iterator, 10);
        $result = array_map(fn($v) => implode('', $v), $result);
        expect($result)->toBe(['0aA!', '1aA!', '0bA!', '1bA!', '0aB!', '1aB!', '0bB!', '1bB!', '0aA"', '1aA"']);
    }
);
/**
 * 指定した範囲の整数を出力するIteratorを生成する。
 * @param int $min 最小値。
 * @param int|null $max 最大値。省略時は無限に値を出す。
 */
function sequence(int $min, int|null $max = null): \Iterator
{
    while (is_null($max) || $min <= $max) {
        yield $min++;
    }
}

/**
 * Iteratorから指定した数の値を取り出してarrayで戻す。
 */
function iterator_take(\Iterator $iterator, int $num): array
{
    if ($num == 0) {
        return [];
    }
    $taken = [];
    foreach ($iterator as $value) {
        $taken[] = $value;
        if (--$num <= 0) {
            break;
        }
    }
    return $taken;
}