どうも関数型の風(微風かな?)が吹き始めているようです(「技術者の技術的教養は変化するのか(しないのか)」参照)。とはいえ、ほとんどの現場で実際に使われているプログラミング言語はせいぜいオブジェクト指向と称するものです。そんな状況ですから、中途半端な過渡的方便としては、“バカバカしくめんどくさい”記述になるのを承知で、現場的言語でファンクショナルな、いやもう一声、カテゴリカルな概念を説明するのも無意味ではないかもしれません(とか言ってみたが、単に興味本位で実は無意味だろう、ダハハハハ)。
Listモナド
それで今日の話題は、Listなんです。型パラメータXを付けたList<X>の形のものね。これは、「型Xを渡すと新たな型を創り出す機能」ですから、「型に型を対応させる関数」ともいえます。
このList<X>は、単に「型→型」対応を与えるだけでなく、独特の(しかし普遍性もある)構造と法則性を持ちます。その構造と法則性はモナドと呼ばれます。ここでの「モナド」は圏論の概念ね。Haskellなどは、プログラミング言語機構としてモナドなるものがあるようですが、僕はよく知らない(が、たぶん根は一緒だろう)。ライプニッツのモナド(単子)とかはさらに知らない(が、関係ねーだろう)。
モナド構造を完全に与えるには、型構成子であるList<X>以外に、flattenとsigletonという関数が必要です。その関数を「Javaで高階プログラミング、ってそれ何よ!」で示しました関数オブジェクトで表現する手もあるけど(そして、そのほうが望ましいのだけど)、ここではstaticメソッドとして書きます。
import java.util.*; public class ListMonad { public static <X> List<X> flatten(List<List<X>> listlist) { List<X> flattenedList = new ArrayList<X>(); for (List<X> list : listlist) { for (X item : list) { flattenedList.add(item); } } return flattenedList; } // singletonの定義 }
flattenは、入れ子のリストの入れ子構造を浅くします。[[a, b], [x, y]] → [a, b, x, y]みたいな操作。singletonは、xから[x]を作る操作ですね。
public static <X> List<X> singleton(X x) { List<X> singletonList = new ArrayList<X>(); singletonList.add(x); return singletonList; }
flattenのmap適用をじかに書く
どんな関数型言語でも、リスト(に相当するデータ構造)とmap関数があります。map(fun, list)は、listの各項目に関数funを適用して、結果を再びリストにして返す操作です。map(fun, [x1, x2, ...]) = [fun(x1), fun(x2), ...] という感じ。
リストのリストのリスト(入れ子リストのリスト)に対しては、map(flatten, listlistlist)が意味を持ちます; map(flatten, [listlist1, listlist2, ...]) = [flatten(listlist1), flatten(listlist2), ...]。しかし、flattenをstaticメソッドで書いてしまったので、flattenを高階関数mapの引数に渡すことはできないので、次善の策として、mapflatten関数をじかに手書きしましょう。
public static <X> List<List<X>> mapflatten(List<List<List<X>>> listlistlist) { List<List<X>> flattenedListList = new ArrayList<List<X>>(); for (List<List<X>> listlist : listlistlist) { flattenedListList.add(flatten(listlist)); } return flattenedListList; }
モナド結合律とモナド単位律
ここで話題が変わりますが; 掛け算×に関する結合律と単位律は次のものです。
- (a×b)×c = a×(b×c)
- a×1 = a
結合律は、「右側を先に計算しても、左側を先に計算しても結果が変わらない」ことを主張しています。単位律は、「1倍する操作(×1を操作とみなす)は何もしないことだ」と言っています。実は、flattenとsingletonに関しても結合律と単位律が成立します。
まず、リストのリストのリストlistlistlistに対して、
- flatten(flatten(listlistlist)) = flatten(mapflatten(listlistlist))
となります。例えば:
flatten(flatten([ [[a, b], [c]], [[], [x, y, z]] ])) = flatten([ [a, b], [c], [], [x, y, z] ]) = [a, b, c, x, y, z] flatten(mapflatten([ [[a, b], [c]], [[], [x, y, z]] ])) = flatten([ flatten([[a, b], [c]]), flatten([[], [x, y, z]]) ]) = flatten([ [a, b, c], [x, y, z] ]) = [a, b, c, x, y, z]
これが結合律です。掛け算の結合律と似ても似つかないって? そんなことないですよ。「内側を先にflattenしても、外側を先にflattenしても結果が変わらない」ってことだから、“左右”が“内外”に変わっただけのことです。
では単位律:
- flatten(sigleton(list)) = list
例えば:
flatten(singleton([a, b])) = flatten([[a, b]]) = [a, b]
掛け算のときは、まずaを考え、(a, 1)というタプルを作り、それに掛け算をしたらもとのaに戻るのでした。ここでは、まずlistを考え、singleton(list)という入れ子リストを作り、それにflattenをしたらもとに戻りました。共通性はあるでしょ。
[追記]掛け算の単位律は、a×1 = a と 1×a = a の2つがあります。掛け算が交換可能でないと(例:行列の掛け算)、この2つは別な法則です。同様に、モナド単位律も実は2つあります。flatten(singleton(list)) = list が1つ、そしてもう1つは、flatten(mapsingleton(list)) = list; mapsingletonは、mapflattenと同様に、singletonをmap化したものです。掛け算が左右2つの単位律だとすると、これは内外2つの単位律ですね(“内外”については結合律のところを参照)。[/追記]
モナドの効用
かなり無理矢理に、モナドの説明をしました。モナド結合律とモナド単位律が、通常の(例えば整数の掛け算の)結合律・単位律とほんとに同類であることを納得するには、相当に抽象的な定式化が必要です。ですが、「計算(操作)順序を問わない」「操作しても何も起こらない(もとに戻る)ような操作がある」という雰囲気は感じられたんじゃないでしょうか。
Listを典型例とするモナド構成は、与えられたデータ構造から新しいデータ構造を創り出し、それに伴って計算や関数の概念も拡張します。例えば、集合Xに1点だけを付け加えるモナド M(X) = X∪{Xに属さない1点} は、部分計算/部分関数の概念を導入します。X上で定義され、一部未定義かも知れない関数(部分関数)f:X→Yは、未定義部分での値を新しい点に再定義して X→M(Y) の関数とみなせます。
モナドは、このような計算概念/関数概念の拡張が、合理的かつ系統的にできることを保証する“構造と法則”というわけです。