檜山正幸のキマイラ飼育記 このページをアンテナに追加 RSSフィード Twitter

キマイラ・サイトは http://www.chimaira.org/です。
トラックバック/コメントは日付を気にせずにどうぞ。
連絡は hiyama{at}chimaira{dot}org へ。
蒸し返し歓迎!
このブログの更新は、Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama
ところで、アーカイブってけっこう便利ですよ。

2006-04-19 (水)

世界で一番か二番くらいにやさしい「モナド入門」

| 16:41 | 世界で一番か二番くらいにやさしい「モナド入門」を含むブックマーク

気まぐれと偶然となりゆきで、ここ2,3回はモナドを話題にしました。googleで「モナド」を引いてザッと眺めると、「モナドはむずかしいー」とか「モナドで挫折した」みたいな雰囲気が感じられて、説明芸人の血が少し騒ぎましたね。「なら、予備知識ゼロでモナドの説明をしてやろうじゃねーか」と。

タイトルはだいぶ煽っちゃった…… けど、ハッタリじゃないつもり…… けど、実際はどうかな?

印刷のときはサイドバーが消えます。

内容:

  1. とりあえず、あたりさわりなくモナドの来歴を紹介する
  2. こんな課題を考えてみよう:副作用付き計算
  3. カウントアップする関数達
  4. カウントアップしたい意志を戻り値で伝える
  5. それでは、いったい誰がカウントアップをするのだ
  6. 関数の引数の型をCountup型にまで拡張する
  7. そして、これがモナド

●とりあえず、あたりさわりなくモナドの来歴を紹介する

今からここで説明する「モナド(monad)」とは、プログラミング言語Haskell圏論におけるモナドです(ライプニッツと直接の関係はありません)。冒頭であんな啖呵を切ったので、前もってHaskell圏論の知識は仮定しませんし、ここ数日の僕のエントリーを読んでいる必要もありません。

プログラミングでモナド機構を使うと、関数、値、計算などの概念を一気に拡張することができます。うーん、ステキ。でも、モナドを採り入れているプログラミング言語の例をHaskell以外は知りません(たぶん他にもあるでしょうが)。そもそも、モナドが少しだけポピュラーになったのもHaskellの影響でしょう。

と、モナドがプログラミングの世界に入ってきたのは比較的最近ですが、理論としては古くて、ソッチ方面(どっち方面かは気にしない)で有名なJ.Beckの論文は1967年です(40年前)。プログラミングへの応用を明確に意識したE.Moggiの論文でさえ、1989年に出てます。

●こんな課題を考えてみよう:副作用付き計算

モナド概念は非常に普遍的なので、モナドの実例はとんでもなくイッパイあります。モナドの実例をいくつか出されると(例えば、リストと状態遷移と例外と入出力)、それらがモナドという単一の概念でくくれること、共通性を持つことが信じがたいでしょう。

そこで、モナドの実例を1つだけ選んで、その特定事例をシッカリ説明することにします。その実例とは副作用付き計算です。副作用とは、関数、メソッド、手続きなど(計算/処理の単位)が、外部(環境)に影響を及ぼすことです。例えば、ローカル変数以外の変数への値のセット、ファイル入出力、画面への描画などは副作用です。

副作用がなくて、純粋に計算だけを行う処理単位を純関数と呼びましょう。純関数の値(計算結果、戻り値)は、その引数値だけで決定されます。同じ引数を渡すなら、いつでもどこでも何度でも同じ値を返します。それが純関数ってもんです。

さて、次の問題を考えましょう:

  • 副作用付き計算を、純関数で表現せよ。

「副作用」と「純関数」の意味を考えると、この問題自体が矛盾した要求で、解決不可能に思えます。にもかかわらず、モナドはみごとな解決策を与えるのです。

●カウントアップする関数達

以下、説明用コードにはJavaScriptを使います。とはいえ、見ればわかるコードなので、JavaScriptの知識もたいして要りません。現状のJavaScriptは型宣言ができないので、コメント内に型を書くことにします。

まずは、大域変数countから:

// count:Number
var count = 0;

ここで、コメント内のcount:Numberは、変数countがNumber型であることを示します。

この変数countをカウンターと呼ぶことにして、カウンターに加算する関数の例を挙げます。

// sum_countup5:Number, Number→Number 副作用あり
function sum_countup5(x, y) {
 count += 5;
 return x + y;
}

関数sum_countup5は、2つの引数を足し算する関数ですが、なぜかついでにカウンターを5だけ上げます。コメント内のNumber, Number→Numberは、2つのNumber型引数を取り、Number型の値を戻すことを示していますが、計算する以外に副作用を持ちます。

js> count
0
js> sum_countup5(1, 3)
4
js> count
5

もう少し例を:

// length_countup:String→Number 副作用あり
function length_countup(s) {
 var len = s.length;
 count += len;
 return len;
}

// countup:Number→Void 副作用あり
function countup(n) {
 count += n;
 return undefined;
} 

関数length_countupが何をするかは見ればわかりますね。関数countupは純関数の対局的存在で副作用だけの処理です。countupの戻り値の型はVoidですが、Void型とは、undefinedという値だけを持つ型だと思ってください。戻り値がない(あるいは不要)なときに使うダミー値がundefinedです。

length_countupとcountupを実行するとこんな感じ:

js> count
5
js> length_countup("Hello, world!")
13
js> count
18
js> countup(3)
js> count
21
js> countup(1)
js> count
22

●カウントアップしたい意志を戻り値で伝える

我々の課題を思い出してください:「副作用付き計算を、純関数で表現せよ」でした。カウンター(大域変数count)に触ることは副作用ですから、これをやめましょう。んじゃ、カウントアップできないじゃないか! って? はい、そのとおり。でも、「カウントアップしたい」という意志を伝えることはできます。計算の結果以外に、カウントアップしたい値(カウンターの増分)も戻り値にします(一種の“多値”ですね)。

さっそくやってみましょう。

function sum_countup5(x, y) {
 return [x + y, 5];
}

まー、これでもいいのですが、単なるペア([3, 5]とか)では一番目の値と二番目の値の役割がハッキリしないので、次にしましょう。

function sum_countup5(x, y) {
 return {value: x + y, countup: 5};
}

これで、sum_countup5(1, 2);とすると、{value: 3, countup: 5}というオブジェクト(構造体と呼ぼうが、マップと呼ぼうが、お好きにどうぞ)が返ってきます。

いま使った {value: なんかの値, countup: 整数値} という形をしたオブジェクトの型をCountup(T)と記すことにします。Tは、「なんかの値の型」が入る場所で、実際には、Countup(Number)型、Countup(String)型、Countup(Void)型のようになります。この書き方だと、sum_countup5の型は次のように記述されます。

// sum_countup5:Number, Number→Countup(Number) 副作用なし

さてと、他の関数もこの方法で書き換えてみましょう。

// length_countup:String→Countup(Number) 副作用なし
function length_countup(s) {
 var len = s.length;
 return {value: len, countup: len};
}

// countup:Number→Countup(Void) 副作用なし
function countup(n) {
 return {value: undefined, countup: n};
}

●それでは、いったい誰がカウントアップをするのだ

これで、副作用を取り除くことができました。定義し直したsum_countup5、length_countup、countupはいずれも純関数です。めでたし、めでたし。オーイ、チョット待て、副作用がなくなったって、それで済ませるなよ!

えーとですね、絶対に誰も大域変数countに触らないって規則だと、さすがに無理なんですよ -- カウントアップできねーよ、それじゃ。それで、一連のカウントアップ要求を最後にホントに実行する処理を書いておきます。

// CountupMain:Countup(T)→T 副作用あり
function CountupMain(countupRequest) {
 count += countupRequest.countup;
 return countupRequest.value;
}

このCountupMainは次のように使います。

js> count = 0
0
js> CountupMain(sum_countup5(1, 2))
3
js> count
5
js> CountupMain(countup(10))
js> count
15

「なんだ、インチキやんけ」って? ウーン、まー少しインチキかもしれない。でもね、インチキ行為はCountupMainが一手に引き受けているわけで、他の関数はすべて純関数として書けるんですよ。つまりだね、CountupMainは、この世の汚辱の一切をただ一人で受け止めている、それにより、民衆はみな天使のようにピュアにすごせる、という、そういう美しい物語なんですよ(プチ感動 …?)。

●関数の引数の型をCountup型にまで拡張する

sum_countup5、length_countup、countupを副作用方式で定義する(最初のほうでやった)場合は、次のような組み合わせ(関数の合成)ができました。

 countup(sum_countup5(1, length_countup("Hello, world!"))

この組み合わせは、とっても正統な組み合わせです。というのも、型チェックを厳密にしても“まったく問題なし”なんです。それを確認するために、関数の型宣言を次のように書いてみます。

Void countup(Number)
Number sum_countup5(Number, Number)
Number length_countup(String)

countup(sum_countup5(1, length_countup("Hello, world!"))は、次(下の図)のように分解できるので、戻り値の型と引数の型がきれいに一致していますね。

Void
↑
countup(Number)
        ↑
        sum_countup5(Number, Number)
                     ↑      ↑
                     1,      length_countup(String)
                                            ↑
                                            "Hello, world!"

ところが、副作用を取り除いたほうはうまくいきません。関数の型が変わってしまいましたからね。

Countup(Void) countup(Number)
Countup(Number) sum_countup5(Number, Number)
Countup(Number) length_countup(String)

もし、次のような型を持つ関数があれば、うまく合成(関数結合)できます。

Countup(Void) countup_ex(Countup(Number))
Countup(Number) sum_countup5_ex(Countup(Number), Countup(Number))

関数名のお尻に「_ex」と付けたのは、extension(拡張)のつもりです。そんな拡張関数を具体的に書いてみれば:

// countup_ex:Countup(Number)→Countup(Void) 
function countup_ex(countup_n) {
 return {value: undefined, countup: countup_n.countup + countup_n.value};
}

// sum_countup5_ex:Countup(Number), Countup(Number) →Countup(Number)
function sum_countup5_ex(countup_x, countup_y) {
 return {value: countup_x.value + countup_y.value, 
         countup: countup_x.countup + countup_y.countup + 5};
}

これで、countup_ex(sum_countup5_ex(1, length_countup("Hello, world!"))がバッチリ定義できる。あっ、ちょっと待て。定数1が困った。sum_countup5_ex(お尻に_exが付いてるぞ!)の第一引数の型はNumberじゃなくて、Countup(Number)なんだよな。しょうがない、整数値からCountup(Number)型のデータを作る関数を作っておこう。

// noeffect:Number→Countup(Number)
function noeffect(n) {
 return {value:n, countup:0};
}

オーシ、やっと目的が達せられるぞ。countup_ex(sum_countup5_ex(noeffect(1), length_countup("Hello, world!"))って式は、型がちゃんと整合している。下の図を見てよーく確認してね!

Countup(Void)
↑
countup_ex(Countup(Number))
          ↑
          sum_countup5_ex(Countup(Number),// 第一引数
                          ↑
                          noeffect(Number)
                                   ↑
                                   1
                          Countup(Number))// 第二引数
                          ↑
                          length_countup(String)
                                         ↑
                                         "Hello, world!"

それでは、いくつかの式をCountupMainに渡してみましょう。あっ、そうだ、見やすさを改善するためにCountupTestって作って、それを使おう。

// CountupTest:Countup(T)→Void
function CountupTest(countupRequest) {
 print("value:" + countupRequest.value);
 print("countup:" + countupRequest.countup);
 count += countupRequest.countup;
 return undefined;
}

js> CountupTest(length_countup("Hello, world!"))
value:13
countup:13
js> CountupTest(noeffect(1))
value:1
countup:0
js> CountupTest(sum_countup5_ex(noeffect(1), length_countup("Hello, world!")))
value:14
countup:18
js> CountupTest(countup_ex(sum_countup5_ex(noeffect(1), length_countup("Hello, world!"))))
value:undefined
countup:32

カウントアップ要求がちゃんと累積されています。一番最後の例だと、length_countupが増分13, sum_countup5_exが増分5を要求し、合計で18。一方countup_exに入る値は(1 + 13) = 14なので、countup_ex自体は増分14を要求し、全体で増分32を要求することになります。

●そして、これがモナド

ここらで今までの経緯をまとめて、モナド概念を正式に導入しておきます。

振り返れば我々は; 関数から副作用を取り除き(汚れ作業はCountupMainに押しつけ)、代わりに戻り値に副作用の意図を詰め込み、それによって失われた関数結合の自由さを関数の拡張により取り戻しました。これらの背後には、次のような約束事/手順があります。

  1. 型TのデータからCountup(T)型のデータを作り出す約束事/手順
  2. fun:T→Countup(S) という関数funを、fun_ex:Countup(T)→Countup(S)に拡張する約束事/手順(funに複数の引数を許すなら、それなりの対応が必要)。
  3. 型Tの値(例えば整数値1)を、Countup(T)型のデータとみなす約束事/手順

今回、一番目の約束事/手順は、{value: T型, countup: 整数型} の形式を使うことにしました。三番目は関数noeffectが処理してますが、その原則は {value: T型, countup: 0に固定} を作るという決まり事です。2番目の関数拡張はそのつど手作業でやってましたが、次のような関数extにより自動化できます。

// ext:(T→Countup(S))→(Countup(T)→Countup(S))
function ext(fun) {
 return function(/* 可変引数 */) {
    var valueArgs = new Array();
    var countupTotal = 0;
    for (var i = 0; i < arguments.length; i++) {
     var arg = arguments[i];
     valueArgs[i] = arg.value;
     countupTotal += arg.countup;
    }
    var result = fun.apply(null, valueArgs);
    result.countup = result.countup + countupTotal;
    return result;
 };
}

関数extを使うと、いちいち手書きしなくても拡張関数を作ってくれます。例えば:

js> var sum_countup5_ex = ext(sum_countup5)
js> var r = sum_countup5_ex({value:5, countup:1}, {value:10, countup:3})
js> r.value
15
js> r.countup
9

以上で出そろった:

  1. 新しいデータ型を構成する約束事/手順であるCountup
  2. fun:T→Countup(S)という関数からext(fun):Countup(T)→Countup(S)という関数を作り出す関数(高階関数)であるext
  3. 型Tの値を、Countup(T)型のデータにする関数noeffect

これらの3つ組(Countup, noeffct, ext)をCountupモナドと呼びます。もちろん、Countupモナドモナドの一例ですが、一般的なモナドも同様で、次の3つで定義されます。

  1. 型Tから新しい型M(T)を創り出す型構成子M
  2. fun:T→M(S)という関数からext(fun):M(T)→M(S)という関数を作り出す関数(高階関数)である(M用の)ext
  3. 型Tの値を、M(T)型のデータにする関数である(M用の)unit

最後の関数の名前をnoeffctからunitに変えたのは、モナド一般の文脈ではnoeffct(作用なし)という名前が不適切だからです。

モナド(M, unit, ext)は、3つ組なら何でもいいわけではなくて、モナド法則という法則を満たす必要があります(今は触れません)。Countupモナドに十分に慣れたなら、他のモナドも学習できるでしょう。そしていずれ、モナドの例が驚くほど多いことや、まったく異なった領域にモナドが出現すること、…などなど、その不思議さ/魅力に触れてみてください。

[追記]このエントリーの補足がコチラにあります。[/追記]

KENZKENZ 2006/04/19 17:44 モナド、興味あったのですが、よくわかっていませんでした。かなりイメージは伝わりました!
ところで、疑問なのですが、実際の副作用はextで作られる拡張関数の中に入るってことでいいんでしょうか?
Countup(T)が副作用のためのコンテキストを保持していて、拡張関数が副作用適用後のコンテキストを計算するってイメージですかね。たぶん。

m-hiyamam-hiyama 2006/04/19 18:04 KENZさん、
> かなりイメージは伝わりました!
説明芸になっていたかな?
> 実際の副作用はextで作られる拡張関数の中に入るってことでいいんでしょうか?
理屈の上では、fun:T→Countup(S)もext(fun):Countup(T)→Countup(S)も副作用を実行しないですよ。どこで誰が副作用を実行するか、なんてことは処理系任せ;ファイル出力のとき、メモリバッファのフラッシュはどのタイミングで誰がやるか(OSかライブラリか俺か)なんてあんまり考えないでしょ。
なんだけど、
> Countup(T)が副作用のためのコンテキストを保持していて、拡張関数が副作用適用後のコンテキストを計算するってイメージですかね。たぶん。
そう思ったほうが精神衛生上いいなら、それでもOKよ。

KMKM 2006/04/19 22:26 (>>=) の動機とか、en.WikiPedia のこれ
http://en.wikipedia.org/wiki/Monads_in_functional_programming
いいかもです

m-hiyamam-hiyama 2006/04/20 10:32 KMさん、まいど。
> http://en.wikipedia.org/wiki/Monads_in_functional_programming
コンパクトによくまとまっている感じですね。

cut-seacut-sea 2006/04/20 11:59 説明芸人だけあってスバラシかったです。
お見事!

m-hiyamam-hiyama 2006/04/20 13:22 cut-seaさん、
> お見事!
ありがとうございます。ウケてよかった。

fhisafhisa 2006/05/23 09:55 おみごと!!
おくればせながら読ませていただきました。関数的プログラミング世界での純関数が、その性質を保ったまま、見えない別世界(Countup世界)に一方通行で作用する、というようなイメージでとらえました。
副作用付き計算とは「まったく異なった領域」を題材にして同じような説明芸を味わいたいです!

m-hiyamam-hiyama 2006/05/23 12:59 fhisaさん、
> 副作用付き計算とは「まったく異なった領域」を題材にして
いやっ、異なる領域つわれても、そんなに守備範囲広くないので、、、、
副作用じゃないモナドとか型クラスとかは続きでなんとかなるかもしれないですけど。あと、束のイデアル論とかゲーデルネタはなんか中途半端にほってあるなぁ。

三輪の牛三輪の牛 2009/06/25 16:12  今までわからなかったMonadを理解するきっかけになりました。
 C#で書いてみました。Extを自動的に適用してくれる構文糖が欲しくなりました。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace MonadTest
{
public class Null
{

}

[DebuggerStepThrough]
public struct Countable<T>
{
public T Value;
public int CountUp;

public Countable(T value, int countUp)
{
Value = value;
CountUp = countUp;
}
}

public static class CountUpTest
{
public static Countable<int> SumCount5(int x, int y)
{
return new Countable<int>(x + y, 5);
}

public static Countable<int> LengthCountUp(string s)
{
var len = s.Length;
return new Countable<int>(len, len);
}

public static Countable<Null> CountUp(int n)
{
return new Countable<Null>(new Null(), n);
}

public static Countable<T> Unit<T>(T n)
{
return new Countable<T>(n, 0);
}

public static Func<Countable<T>, Countable<S>> Ext<T, S>(Func<T, Countable<S>> fun)
{
return source => {
var result = fun(source.Value);
result.CountUp += source.CountUp;
return result;
};
}

public static Func<Countable<T1>, Countable<T2>, Countable<S>> Ext<T1, T2, S>(Func<T1, T2, Countable<S>> fun)
{
return (t1, t2) => {
var result = fun(t1.Value, t2.Value);
result.CountUp += t1.CountUp + t2.CountUp;
return result;
};
}

public static void CountupTest<T>(Countable<T> countupRequest)
{
Console.WriteLine("Value:" + countupRequest.Value);
Console.WriteLine("CountUp:" + countupRequest.CountUp);
}

public static void Test()
{
var SumCounUp5Ex = Ext<int, int, int>(SumCount5);
var LengthCountUpEx = Ext<string, int>(LengthCountUp);
var CountUpEx = Ext<int, Null>(CountUp);

CountupTest(LengthCountUp("Hello, world!"));
CountupTest(Unit(1));
CountupTest(SumCounUp5Ex(Unit(1), LengthCountUp("Hello, world!")));
CountupTest(CountUpEx(SumCounUp5Ex(Unit(1), LengthCountUp("Hello, world!"))));
}
}
}

m-hiyamam-hiyama 2009/06/26 08:53 三輪の牛さん、
> 今までわからなかったMonadを理解するきっかけになりました。
お役に立てたんら、幸いです。
> C#で書いてみました。Extを自動的に適用してくれる構文糖が欲しくなりました。
手作業でもモナドの実装はできるんですが、メンドクサイのでプログラミング言語のサポートが欲しくなりますよね。