📂プログラミング

マップとリデュースを用いたプログラミング

定義

マップ

関数 $f : X \to Y$ の集合を$F$としよう。以下のように定義される高階関数 $\text{map}$ をマップという。 $$\text{map} : F \times 2^{X} \to 2^{Y} \\ \text{map} \left( f , \left\{ x_{1} , \cdots , x_{n} \right\} \right) := \left\{ f \left( x_{1} \right) , \cdots, f \left( x_{n} \right) \right\}$$

フォールド

関数 $g : X \to X$ の集合を$G$としよう。以下のように定義される高階関数 $\text{fold}$ をフォールドという。

$$\text{fold} : G \times 2^{X} \to X \\ \text{fold} \left( g , A \right) := g \left( x , \text{fold} \left( g , A \setminus \left\{ x \right\} \right) \right) \qquad , x \in A$$

説明

定義に出てくる数式は、数学をする人たちが理解しやすいように書かれただけだから、あまり驚かないでほしい。簡単に言うと、マップは受け取った配列の各要素に受け取った関数を適用する関数であり、フォールドは配列の要素を一つずつ取り出して^pop与えられた関数を続けて適用する関数だ。

フォールドの数式が難しいと感じるなら、ウィキペディアの説明を参照してみよう。十分に難しいので、数式が簡単に見える効果があるだろう。

関数型プログラミングでは、フォールドは高階関数の系列の一つであり、再帰的なデータ構造を分析し、受け取った結合操作を使用して再結合し、再帰的に実行されたその結果で戻り値を生成する。フォールドは通常、関数をデータ構造の最上位ノードの結合関数の形で表され、特定の条件下で使用できる何らかのデフォルト値を持つことができる。そして、その関数を使用して、データ構造の階層上の要素を系統的に結合する過程を進める。

マップとフォールドは、どちらも関数を引数に取る高階関数であり、特にフォールドは再帰関数だ。このポストのタイトルが示すように、フォールドは通常リデュース^reduceと呼ばれる。

マップとリデュースは、関数型プログラミングを受け入れることで得られる利点の一つとされ、ハドゥープ^hadoopや分散コンピューティングなどの場所で触れることができる。効率は落ちるが、多数のスレーブ^slaveノード各々でデータを処理（マップ）し、そのデータをマスター^masterノードで集約して要約する（リデュース）イメージを思い浮かべればいい。

例

マップ：ブロードキャスティング

プログラミング言語の一つであるジュリアでは、マップを日常的に使用し、マップをネイティブに使用できる文法をブロードキャスティング^broadcastingと呼ぶ。

julia> A = [1,-2,3,-4]
4-element Vector{Int64}:
  1
 -2
  3
 -4

julia> f(x) = x^2
f (generic function with 1 method)

例えば、配列 Aと関数 f()があれば、map()は次のように配列の各要素にfを適用する。

julia> map(f, A)
4-element Vector{Int64}:
  1
  4
  9
 16

その一方で、同じ原理、同じ結果だが、次のようにfの後にドット.を付けてAの要素にポイントワイズ^pointwiseにfを適用することもできる。これがブロードキャスティングだ。

julia> f.(A)
4-element Vector{Int64}:
  1
  4
  9
 16

フォールド：リデュース

これ以上の説明は必要ない。直接見れば一発で理解できる。

julia> reduce(+, A)
-2

$$\text{reduce} (+,A) = -4 + (3 + ((-2) + 1)) = -2$$

julia> reduce(max, A)
3

$$\text{reduce} (\max,A) = \max(-4 , \max(3 , \max (-2 , 1))) = 3$$