ペア、リスト、cons

ペア、リスト、cons - javascript 2012/03/23(Fri.)
値の列、つまりリストを実装するのに、
LISPなど関数型言語ではペアの連結によって これを実現する。
すなわちペアとは二つの値 (value1, value2) という
組み（組みが集合とは異なるのは順序が保存されること）のこと。

Schemeでコレをならった時、 '(v1 . v2)
と書いたな、そういえば。

[v1, v2, v3]というリストは
p = (v2, v3)をまず用意して (v1 , p)とすればよい。
pを展開すれば (v1, (v2, v3))である。
つまり、ペアの２つ目の値を次のペアにした。
しかし最後だけ、ここではリストの最後の要素v3だけが、ペアの二つ目に入っている。
其れ以外はペアの一つ目なのに。これは整然とならないので、空のペア ()
を用いる。NULに相当する何かである。
(v1, (v2, (v3, ())))

要素がnコの場合のリストに容易に拡張するコトができるであろう。
最後の空ペアのカッコも含めれば (n + 1)コのカッコで一つの配列ができる。

一つのリストに対しては任意の操作は三つの関数によって実現できる。
すなわち cons
car
cdrである。

consはペアを作るものであり、リストに対しては先頭への追加を表現する。
cons(1, 2)
これは 1, 2を取ってペア '(1 . 2)を作った。
リストの操作としては次のほうが大切で
リスト a に対して cons(1, a)は やはり、 '(1 . a)
であるが、これはリストaの先頭に1という要素を加えたものである。

リストの最後に要素を加える、あるいは途中の任意の箇所に挿入するのは
再帰的にどうにかするしかない。なんでこんなことするの？って死にたくなる。

疲れた。
というかこんなことが書きたかったわけじゃない。

car, cdrはそれぞれ、引数として取ったペアの一つ目、２つ目を返す。
リストを渡せばcarはリストの先頭要素を返し、cdrはリストの先頭要素を
除いた、つまり２つ目以降のリストを返すことになる。
carとかcdrという名前は何かの略。

var a = cons(1, cons(2, cons(3, ())))
car(a) // 1
cdr(a) // '(2 . (3 . ()))

本題。
なんで関数型ならこんなことをするのだろう。偶然ネットで教えてもらった
ことには、cons,car,cdrはリストを関数値として割と簡単に定義できるから。
function cons(x, y) {
    return function(f){return f(x, y)};
}
function car(z) {
    return z( function(x, y){
        return x;
    });
}
function cdr(z) {
    return z( function(x, y){
        return y;
    });
}
一回書いてみてたらなぁんだこんなことか、なのだけど、試しに
ペアを入れ子にしてリストを作ってみたら、ちょっと感動した。

ちゃんと関数の引数をバインドしてるんだよね。でも
var a = cons(1, 2);
としてaをFirebugで見てみても1,2という数字が見えない…？

テスト。
a = cons(1, 2);
b = cons(0, a);
cdr(cdr(b)); // 2

中身が空のカッコなんて掛けないのでnullを用いてリストを表現することにする。
list = cons(1, cons(2, cons(3, null)))

このようなリストについて要素を順番に示す文字列に変換する手続きtoStringは
次のようなものだろう。再帰的にcdrを呼び出して行ってnullなら終了すればイイ。

function ToString(list, str){
    if(!list) return str + "())";
    if(!str) str = "(";
    return ToString(cdr(list), str + car(list) + " . ");
}
ToString(list); // "(1 . 2 . 3 . ())"
二引数目のstrを最初の呼び出しではundefinedなのでコレでいい。

appendとは二つのリストの結合という操作を示す。
これも再帰的に作ることになる。
結局carもconsも先頭から読み先頭へ追加しかできないのが窮屈なんだよね。
でもリストを連結するにはどっちかは後ろから読んで先頭につけないといけない。

単純に一つのリストについて先頭から読みだして新しいリストに
先頭につけていけば逆順にする操作reverseが実現できる。
function reverse(list, new_l){
    if(!list) return new_l;
    if(!new_l) new_l = null;
    return reverse(cdr(list), cons(car(list), new_l));
}

ToString(reverse(list)); // "(3 . 2 . 1 . ())"

で、リストの結合をするには、list1 + list2 をするならば、
list1をreverseして、それを先頭から読みだしてlist2の頭に
くっつけていけばできそう。
function append(list1, list2){
    return (function(l1, l2){
        if(!l1) return l2;
        return arguments.callee(cdr(l1), cons(car(l1), l2));
    })(reverse(list1), list2);
}
list1 = cons(1, cons(2, cons(3, null)));
list2 = cons("a", cons("b", cons("c", null)));

ToString(append(list1, list2)); // "(1 . 2 . 3 . a . b . c . ())"
コメ(0) | トラ(0)
intime o'
