Jsmanga

データ構造と「三種の神器」関数

多くのカッコいいプログラミング言語には、データ構造(配列など)を操作するときに便利な三種類の関数があります。 for ループの説明もあわせて簡単に紹介します。

filter

名前の通り、ある条件に合う値だけを取りだします。 filter 関数の入力は真偽値(trueかfalse)を出力する関数です。

const a = [1, 2, 3, 4, 5];

a.filter(x => x < 3); // => [ 1, 2 ]

map

入力の関数を、配列の中身に適用した結果を出力する関数です。

const a = [1, 2, 3, 4, 5];
const fact = x => x == 1 ? 1 : x * fact(x - 1);

a.filter(x => x != 3).map(fact); // => [ 1, 2, 24, 120 ]

reduce

入力の関数を、配列の中身と途中結果に適用した結果を出力します。配列中の最大値を調べる例を使って説明しましょう。

const a = [1, 2, 300, 4, 5];
const max = (x, y) => x > y ? x : y

a.reduce(max); // => 300

// reduce の動作: 左端と途中結果を関数に入れた結果を求めていく
[max(1, 2), 300, 4, 5] // => [300, 4, 5].reduce(max, 2)
[max(2, 300), 4, 5]    // => [4, 5].reduce(max, 300)
[max(300, 4), 5]       // => [5].reduce(max, 300)
[max(300, 5)]          // => 300

※ 第2引数はデフォルトで配列の先頭が入ってます。 reduce は三種の神器でも、慣れが必要ですが使えるところは多いです。右から畳み込まれる reduceRight という関数も用意されています。

再帰関数とデータ構造

三種の神器を使って、ベクトルや行列演算を定義してみましょう。

$$ [a_{1}, \dots, a_{n}] + [b_{1}, \dots, b_{n}] = [a_{1} + b_{1}, \dots, a_{n} + b_{n} ] $$

$$ \begin{bmatrix} [a_{11}, \dots, a_{1n}] \\ \vdots \\ [a_{n1}, \dots, a_{nn}] \end{bmatrix} + \begin{bmatrix} [b_{11}, \dots, b_{1n}] \\ \vdots \\ [b_{n1}, \dots, b_{nn}] \end{bmatrix} = \begin{bmatrix} [a_{11} + b_{11}, \dots, a_{1n} + b_{1n}] \\ \vdots \\ [a_{n1} + b_{n1}, \dots, a_{nn} + b_{nn}] \end{bmatrix} $$

ベクトル (上式) とはまさに配列です。二次元の行列 (下式) は配列の配列で表せます。さらに配列の配列の...の配列という多次元配列をテンソルと呼びます。ベクトルは一階のテンソル、行列は二階のテンソルとも呼びます。

このような入り組んだデータ構造の演算には再帰関数が適役です。

// 二項演算を作る高階関数
const vec_op = op =>
{
    const loop = (x, y) =>
        x.map((value, index) =>
            Array.isArray(value)
                ? loop(x[index], y[index])  // 配列なら潜る
                : op(x[index], y[index])    // 配列でないなら演算
    );
    return loop;
}

// 加算
const vec_add = vec_op((x, y) => x + y);
// 減算
const vec_sub = vec_op((x, y) => x - y);

const a = [[1, 2],
           [3, 4]];
const b = [[1, 0],
           [0, 1]];

vec_add(a, b); // => [[2, 2], [3, 5]]
vec_sub(a, b); // => [[0, 2], [3, 3]]

ついに再帰関数を返す高階関数がでできました！何次元でも演算できますヤター。

filter/map/reduce 関数の作り方

for ループや再帰関数の使い方の確認がてら作ってみましょう (もちろん、普段は標準のものを使ってください)。

// filter - 再帰
const filter = (a, f) => a.length == 0
    ? []
    : f(a[0])
        ? Array.concat(a[0], filter(a.slice(1), f))
        : filter(a.slice(1), f);


// filter - for ループ
const filter_for = (a, f) =>
{
    let b = [];
    for (let i = 0; i < a.length; ++i)
    {
        if (f(a[i]))
        {
            b.push(a[i]);
        }
    }
    return b;
};


// map - 再帰
const map = (a, f) => a.length == 0
    ? []
    : Array.concat(f(a[0]), map(a.slice(1), f));  

// map - for ループ
const map_for = (a, f) =>
{
    let b = [];
    for (let i = 0; i < a.length; ++i)
    {
        b.push(f(a[i]));
    }
    return b;
};


// reduce - 再帰
const reduce = (a, f, acc = a[0]) => a.length == 0
    ? acc
    : reduce(a.slice(1), f, f(acc, a[0]));

// reduce で filter/map は作れる
const filter = (a, f) =>
    reduce(a, (acc, x) => f(x) ? acc.push(x) : acc, []);

const map = (a, f) =>
    reduce(a, (acc, x) => acc.push(f(x)), []);

以上の自前の関数を使うには、次のようになります。あれ、なんかさっきの奴らと違いますね？

const a = [1, 2, 3];
const f = x => x + 2;

map(a, f); // => [3, 4, 5]

次回は、標準の map/reduce/filter のように使う方法をご紹介しましょう。それでは。