JavaScriptの関数だけで、データ構造を書いたみた
データ構造と関数
今回は、タイトルのとおり、データ構造を関数だけで書いてみたというお話です。この記事では、リスト構造を書くことを目指します。ついでに、条件分岐と繰り返しも関数だけで書いてみましょう。
http://jwodder.freeshell.org/lambda.htmlのメモを参照しています（実証を兼ねて）
言語にJavaScriptを使いますが、基本的なスコープ（スコープチェーンの仕組みなど）を知っていれば初心者でもOKです。
真偽値を関数で表現
まず、手始めに、真偽値を関数だけで書きます。この関数はあとで使います。
trueオブジェクトの代わりに、True関数をコードで書きましょう。同様に、False関数も書いておきます。
var True = function (t) {
return function (f) {
return t;
};
};
var False = function (t) {
return function (f) {
return f;
};
};
二つの真偽を表す関数の呼び出し方はこうです。
True(12)(15); // 12 False(12)(15); // 15
さらに、if文の代用品として、If関数を作ります。
var If = function(bool) {
return function(t) {
return function(f) {
return bool(t)(f);
};
};
};
それで、これにTrue関数やFalse関数を入れてやると、if文と似たことができます。
/*条件が真の場合*/
var s = If (True) (
function(x) {
return x;
}
) (
function(x) {
return x + 1;
}
);
/*条件が偽の場合*/
var sa = If (False) (
function(x) {
return x;
}
) (
function(x) {
return x + 1;
}
);
s(12); // 12
sa(12); // 13
どういうことかというと、JavaScriptで、関数だけで、条件分岐ができるということです。If関数は、真（True関数）だったら、一番目に入力した関数を返します。偽（False関数）だったら、2番目の関数を返します。
And関数とOr関数はまた別の機会に説明します。
木構造を関数だけで
さらに、Pair関数を作りましょう。この関数は二つのデータを、ペアとして組ませることができる便利なものです。
var Pair = function (first) {
return function (second) {
return function (bool) {
return bool(first)(second);
};
};
};
Pair関数を使うには、前述のTrue関数とFalse関数を使います。
var s = Pair(12)(15); // 数値のデータ、12と15の二つをペアとして組んだ s(True); // 12 s(False); // 15
TrueやFalseだと分かりにくいので、二つのデータを取り出したいときには、次のFirst関数とSecond関数を使います。
ちなみに、First関数は一番目のデータ (上の例では 12)を取り出すことができます
var First = function (p) {
return p(True);
};
var Second = function (p) {
return p(False);
};
var s = Pair(12)(15); // 数値のデータ、12と15の二つをペアとして組んだ
First(s); // 12
また、Second関数を使うと、二番目のデータである15を返します。
Second(s); // 15
これで、木構造も作れますが、今回はリスト構造を作ってみましょう。
リスト構造
このPair関数を以下のように並べていくと、リスト構造を作ることができます。
var list = Pair( 12 )(
Pair( 15 )(
Pair( 18 )(
Empty
)
)
);
Emptyは「もうリストがないよ。中身が空だよ」の意味です。これをlistの前に、関数でコーディングしておきます。
var Empty = function(x) {
return True;
};
var list = Pair(12)/*以下、省略...*/
Second関数を何度も使ってデータを呼び出すと、Second(Second(...と書くようになりますので、Index関数を使います。
var Index = function (t) {
return function (i) {
return First (
i(Second)(t)
);
};
};
Index関数の引数iには、関数として作っておいた数値を入れれば大丈夫です。たとえば、次のコードのような感じです。
var _0 = function (f) {
return function (x) {
return x;
};
},
_1 = function(f) {
return function(x) {
return f(x);
};
},
_2 = function(f) {
return function(x) {
return f(f(x));
};
};
Index(list)(_0); //インデックスが一番目の12を返す
Index(list)(_1); //二番目の15を返す
Index(list)(_2); //三番目の18を返す
空リストについて
リストが空なのか、中身があるのかを見分けられるisEmpty関数をつくります。
var Empty = function(x) {
return True;
};
/*Emptyかどうか判別できるisEmpty関数*/
var isEmpty = function(t) {
return t (
function (x) {
return function (y) {
return False;
};
}
);
};
以下、使い方です。
isEmpty(Empty); // True isEmpty(Pair(12)(15)); // False
つまり、Emptyではないもの、たとえば、Pair関数で作られたものが入力されたとき、isEmpty関数はFalseを返します。Emptyのときには必ずTrueを返すのです。
なぜ、Empty関数が空リストの役目を果たせるのか分かりましたら、次は、これを使って、リストのMap関数を作ってみましょう。
リストに関数を適用させて、新しいリストを作るMap関数
Map関数を作る前に、If関数を改良したSelect関数を作ります。この関数は私が作ったのですが、かなり重要です。
var Select = function(bool) {
return function(t) {
return function(f) {
return bool(t)(f)(bool);
};
};
};
Select関数は、If関数と比べて、直接、値を返すのではなく、一度、関数を実行してから、その返り値を返すようにします。以下の比較例をご覧ください。
var t = If (True) (
12
) (
15
);
t; // 12
var s = Select (True) (
function(x) {
return 12;
}
) (
function(x) {
return 15;
}
);
s; // 12
もうひとつ、Select関数とは別に、下ごしらえとして、入力した関数を繰り返しループできるRepeat関数を作ってみます。
var Repeat = function (f) {
/*__f関数は巻き上げ関数を利用したインライン関数
* コードを見やすくするために、インラインを使っている*/
return __f(__f);
function __f(x) {
return f(
function(y) {
return (x(x))(y);
}
);
};
};
使い方は、「ループさせておきたい関数を返すような関数」をRepeat関数に入れれば、OKです。ループの停止条件は、引数itを関数として実行させないようにすることです。
var o = Repeat( function(it) {
/*function (n) {...から始まる関数が繰り返される*/
return function (n) {
if (n < 5) {
return n + it(n+1);
} else {
/*itが実行されていないので、ループはここで停止*/
return n;
}
};
}
);
o(1); // 15 = 1 + 2 + 3 + 4 + 5
また、it(m) を実行したとき、その引数 m はループ対象の引数 n へ引き渡されます。
上の例では、if文を使いましたが、次は、Select関数を使うことになります。
さて、これまで作っておいたSelect関数とRepeat関数の二つを使って、Map関数を作りましょう。
var Map = Repeat (function (it) {
/*リピート対象はfunction (f) {...から始まる関数*/
return function (f) {
return function(t) {
return Select( isEmpty(t) )(
/*Trueの場合、この関数が実行される*/
function(x) {
return Empty;
}
) (
/*Falseの場合、この関数が実行される*/
function(x) {
return Pair (
f (
First (t)
)
) (
it(f)(
Second (t)
)
);
}
)
};
};
});
さっそく、実験です。リストのそれぞれの項目に+1をしてみたいと思います。
var newList = Map(
function(x) {
return x + 1;
}
) (
list
);
Index(newList)(_0); // 13 = 12 + 1
Index(newList)(_1); // 16 = 15 + 1
Index(newList)(_2); // 19 = 18 + 1
あとがき
今回は、プログラミングの世界でよく知られている、真偽値、数値、リスト構造などをJavaScriptの関数として表現できることを示しました。すなわち、
- 条件分岐や繰り返しなどの制御構造
- リストなどのデータ構造
- 数値
の三つは、関数として書き直すことができるということです。
もちろん、さらなる検証が求められます。
次
参考サイト
以下のサイトで学びました。謝意を述べます。ありがとうございました
- 「JavaScriptで学ぶ・プログラマのためのラムダ計算」
http://d.hatena.ne.jp/m-hiyama/20070208/1170905900
- 「ラムダ計算をちょっと勉強してみたので、忘れないうちに書いておく」
http://naokirin.hatenablog.com/entry/20120309/1331286179
- 「『ラムダ計算』を独学で学習するための，講義ノートやPDFのリンク集 （復習用の問題付き）」
http://language-and-engineering.hatenablog.jp/entry/20130313/LambdaCalculusBasicNoteLinks
