PHPで無限ストリームの直積(4)

前回→
terazzo.hatenadiary.org
まあここからはほぼ蛇足だけど、前回のものをIteratorに有限のものが混ざっていても大丈夫なように修正する。

初回の時の図を思い出しながら、これの片方が有限の場合で考えてみる。

↓↓↓↓↓

増えたaに対して過去のbの全値を掛け合わせていけばいいですね。

プログラムを見直すと、まずIteratorを同時に回しているところを修正し「どれか一つでも次の値がある場合にループを続けるようにする」のと、「次の値がない場合は出力済みの値を出し続ける」ように直せば良そう。

function gradual_iterator(iterable $iter): \Iterator
{
    $cached = [];
    foreach ($iter as $last) {
        yield [$cached, [$last], true];
        $cached[] = $last;
    }
    // 値が尽きても出し続ける(validかどうかは戻り値で渡す)
    while (true) {
        yield [$cached, [], false];
    }
}

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にしている。
新規の値があるかをvalid()じゃなくて値で判定するのはIteratorとしては行儀が悪い気はしますね。判定と過去の値を保持するのを同時にやりたいのでこうなってる。

function iterator_cartesian_product(iterable ...$iterators): \Iterator
{
    foreach (gradual_iterator_zip(...$iterators) as $dimensions) {
        $configurations = array_cartesian_product(...$dimensions);
        array_shift($configurations); // 出力済みの値をスキップ
        foreach ($configurations as $configuration) {
            yield from array_cartesian_product(...$configuration);
        }
    }
}

テスト

    public function test_iterator_product2_finite()
    {
        $iterator = iterator_cartesian_product(sequence(0), sequence(0, 2));
        $result = iterator_take($iterator, 15);
        $expected = [[0, 0], [1, 0], [0, 1], [1, 1], [2, 0], [2, 1], [0, 2], [1, 2], [2, 2], [3, 0], [3, 1], [3, 2], [4, 0], [4, 1], [4, 2]];
        $this->assertEquals($expected, $result);
    }

折角Generatorを使った遅延評価なのにarray_cartesian_productがばかでかい配列を作るのでメモリが足りなくなるのがイマイチですね。

PHPで無限ストリームの直積(3)

前回→
terazzo.hatenadiary.org
無限ストリーム(Iterator)の直積を4個以上にも対応していきたい。
方針を立てるために前回のストリーム3個の場合のコードを見ながら、引き続き各Iteratorを「次元」、値のリストを「辺」、値を「点」とみなすメタファーを使って疑似コードを書いてみる。

function iterator_cartesian_product(\Iterator ...$iters): \Iterator
{
    // ①引数を生成済みの値を段階的に出力するIteratorに変換
    $gradual_iters = array_map(gradual_iterator(...), $iterators):
    // ②それを同時に進行するIteratorを作ってforeachで回す
    foreach(iterator_zip(...$gradual_iters) as $dimensions) {
        ③各次元の値を「辺(出力済みの値のリスト)」と「点(新たに出力された値)」に分解
        ④各次元から辺または点のどちらかを選んだすべての組み合わせのリストを作成
        foreach(④ as 各次元から辺または点のどちらかを選んだリスト) {
            if (すべてが辺) continue; // 出力済み
            ⑤ yield from [点,点,点...]のリスト
        }
    }
}

⑤の部分が有限リストの直積で出せそうだが、④の各次元から辺or点を選ぶ部分ももよく見たら直積(2×2×...)になってる。これを「閑話休題 - terazzoの日記」の配列の直積で書いてみる。

その前に準備としてgradual_iterator()を直して[出力済みの値のリスト,[新たな値]]を出すようにする。あとから分解するの面倒だからね。

function gradual_iterator(\Iterator $iter): \Iterator
{
    $cached = [];
    foreach ($iter as $last) {
        yield [$cached, [$last]];
        $cached[] = $last;
    }
}
// こっちは変更なし
function iterator_zip(\Iterator ...$iterators): \Iterator
{
    while (array_reduce($iterators, fn($acc, $iter) => $acc && $iter->valid(), true)) {
        yield array_map(fn($iter) => $iter->current(), $iterators);
        array_walk($iterators, fn($iter) => $iter->next());
    }
}

これとこの前作った配列の直積を出す関数を使って

function array_cartesian_product(array ...$arrs): array
{
    return array_reduce($arrs, fn($acc, $arr) => array_reduce(array_map(fn($v) => array_map(fn($r) => [...$r, $v], $acc), $arr), array_merge(...), []),[[]]);
}

すると無限ストリーム(Iterator)の直積は以下のように書ける

function iterator_cartesian_product(\Iterator ...$iterators): \Iterator
{
    foreach (iterator_zip(...array_map(gradual_iterator(...), $iterators)) as $dimensions) {
        $configurations = array_cartesian_product(...$dimensions);
        array_shift($configurations);
        foreach ($configurations as $configuration) {
            yield from array_cartesian_product(...$configuration);
        }
    }
}

$configurations(各次元から辺または点を選んだもの)の一つ目はすべて辺(出力済みの値)なのでarray_shiftで除去しています。手抜きだね。
内側のforeachはarray_mapとarray_mergeでも書けるけどメモリすごく食うのでforeachで十分。

テストとしてシーケンス4個をproductして最初の10個と9991～10000個目をみてみる。

    public function test_iterator_product()
    {
        $iterator = iterator_cartesian_product(sequence(0), sequence(0), sequence(0), sequence(0));
        $result = iterator_take($iterator, 10000);
        $result = array_map(fn($v) => implode('', $v), $result);
        $head10 = array_slice($result, 0, 10);
        $tail10 = array_slice($result, -10);
        $this->assertEquals(['0000', '1000', '0100', '1100', '0010', '1010', '0110', '1110', '0001', '1001'], $head10);
        $this->assertEquals(['0999', '1999', '2999', '3999', '4999', '5999', '6999', '7999', '8999', '9999'], $tail10);
    }

ちゃんと網羅できてるっぽい。
有限のIteratorが混ざってる場合にも対応したいですね。

閑話休題

その1. PHPで配列の直積

複数配列の直積、ワンラインで書けますね。

function array_cartesian_product(array ...$arrs): array
{
    return array_reduce($arrs, fn($acc, $arr) => array_reduce(array_map(fn($v) => array_map(fn($r) => [...$r, $v], $acc), $arr), array_merge(...), []),[[]]);
}

可変長引数の代わりに各配列にラベルをつけるために連想配列で渡して結果もラベル付き(連想配列)で受け取れる感じにしたかったらこう↓

/**
 * array_reduce()の連想配列版。$callbackを呼び出す際に第3引数としてキーを渡す。
 */
function assoc_reduce(array $assoc, callable $callback, mixed $acc = null): mixed
{
    foreach ($assoc as $key => $value) {
        $acc = $callback($acc, $value, $key);
    }
    return $acc;
}
/**
 * 配列を値として取る連想配列の直積を取り、各配列のキーを値に付与したものの配列を戻す。
 */
function assoc_cartesian_product(array $assoc): array
{
    return assoc_reduce(
        $assoc,
        fn($acc, $array, $key) => array_reduce(
            array_map(fn($value) => array_map(
                fn($r) => $r + [$key => $value],
                $acc
            ), $array),
            array_merge(...),
            []
        ),
        [[]]
    );
}

流石に見にくいので改行した(IDEさんが)
こんな感じで連想配列の配列で受け取れる

    public function test_assoc_cartesian_product()
    {
        $result = assoc_cartesian_product(
            [
                'digit' => [0, 1],
                'ab'    => ['a', 'b'],
                'sign'  => ['+', '-']
            ]
        );

        $this->assertEquals(
            [
                ['digit' => 0, 'ab' => 'a', 'sign' => '+'],
                ['digit' => 1, 'ab' => 'a', 'sign' => '+'],
                ['digit' => 0, 'ab' => 'b', 'sign' => '+'],
                ['digit' => 1, 'ab' => 'b', 'sign' => '+'],
                ['digit' => 0, 'ab' => 'a', 'sign' => '-'],
                ['digit' => 1, 'ab' => 'a', 'sign' => '-'],
                ['digit' => 0, 'ab' => 'b', 'sign' => '-'],
                ['digit' => 1, 'ab' => 'b', 'sign' => '-']
            ],
            $result
        );
    }

その2. array_all()

array_reduce($iterators, fn($acc, $iter) => $acc && $iter->valid(), true)

こういうの、PHP8.4以降だとarray_allで書けるらしい。

array_all($iterators, fn($iter) => $iter->valid())

簡潔だし、一つでもfalseがあればそこで止まるので経済。
参考: PHP: array_all - Manual

PHPで無限ストリームの直積(2)

前回Iterator2個を先頭から読んで要素同士を組み合わせたすべての値を生成するIteratorを作成した。
terazzo.hatenadiary.org
今回はこれを3個に増やしてみる。

PHPで無限ストリームの直積(1)

PHPで2個の配列から一つづつ値を取り出した際の全ての組み合わせを取得したい場合はforeachを入れ子にすればいい。

$arr1 = [0, 1, 2];
$arr2 = ['a', 'b', 'c'];
$product = iterator_to_array((function ($a1, $a2) {
    foreach ($a1 as $v1) {
        foreach ($a2 as $v2) {
            yield [$v1, $v2];
        }
    }
})($arr1, $arr2));
echo "[[" . implode("],[", array_map(fn($arr) => implode(",", $arr), $product)) . "]]\n";
// => [[0,a],[0,b],[0,c],[1,a],[1,b],[1,c],[2,a],[2,b],[2,c]]

でも片方が無限に値を出すIteratorの場合はこれだと上手くいかないのでどうすればいいか。

なんかHaskellで似たようなの見たことあったなと思って検索したらあった。

そこで、下図に示すように、対角線上に組を生成していくことにします。

お気楽 Haskell プログラミング入門

リスト : 組の生成 (2)

pair_stream' :: [a] -> [b] -> [(a, b)]
pair_stream' xs ys = makePair 1 xs ys where
  makePair n xs ys = zip (take n xs) (reverse (take n ys)) ++ makePair (n + 1) xs ys

なるほど！かしこいですね！真似しよう。

PHPのIteratorだと途中でrewindができない場合がある(Generatorなど)ので工夫がいる。

まず準備として、無限Iteratorを段階的に値を出すIteratorにするIteratorを作る。たとえば[1,2,3,4...]の場合は、[[1],[1,2],[1,2,3],[1,2,3,4],...みたいな感じで出す。一度生成した値をキャッシュしておけばいいよね。

function gradual_iterator(\Iterator $iter): \Iterator
{
    $cached = [];
    foreach ($iter as $val) {
        $cached[] = $val;
        yield $cached;
    }
}

あと、2個のIteratorを同時に回したいのでzipする関数も作っておく。

/**
 * 複数のIteratorを同時に進行させてそれぞれの生成した値を組にしたarrayで取り出す。
 * Iteratorのうち一つでもvalid()でなくなればそこで止める。
 */
function iterator_zip(\Iterator ...$iterators): \Iterator
{
    while (array_reduce($iterators, fn($acc, $iter) => $acc && $iter->valid(), true)) {
        yield array_map(fn($iter) => $iter->current(), $iterators);
        array_walk($iterators, fn($iter) => $iter->next());
    }
}

pair_streamを写経

function pair_stream(\Iterator $iter1, \Iterator $iter2): \Iterator
{
    foreach (iterator_zip(gradual_iterator($iter1), gradual_iterator($iter2)) as [$xs, $ys]) {
        yield from array_map(null, iterator_to_array($xs), array_reverse(iterator_to_array($ys)));
    }
}

ちゃんと動く？確認用のヘルパー関数を作ってテスト。

/**
 * 指定した範囲の整数を出力する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;
}

    public function testIterator()
    {
        $iter1 = sequence(1);
        $iter2 = sequence(1);
        $result = pair_stream($iter1, $iter2);
        $expect = [[1,1],[1,2],[2,1],[1,3],[2,2],[3,1],[1,4],[2,3],[3,2],[4,1],[1,5],[2,4],[3,3],
 [4,2],[5,1],[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[1,7],[2,6],[3,5],[4,4],[5,3],
 [6,2],[7,1],[1,8],[2,7],[3,6],[4,5],[5,4],[6,3],[7,2],[8,1],[1,9],[2,8],[3,7],
 [4,6],[5,5],[6,4],[7,3],[8,2],[9,1],[1,10],[2,9],[3,8],[4,7],[5,6]];
        $this->assertEquals($expect, iterator_take($result, 50));
    }

ちゃんと動いてるっぽい。

[Scala] Re: Mapの置換にみるジェネリクス表現

お題:

Map を Mapに変換するメソッドを作るという話題。

Mapの置換にみるジェネリクス表現 - プログラマーの脳みそ

元の話はJavaなんだけどScalaではできるかどうかやってみた。
バージョンはScala 2.11.2

â–

久しぶりなのでリハビリが必要