squirrel_code @ ウィキ
無限リスト
最終更新：
squirrel_code
-
view
無限リスト
last update: 2012/12/06 (Thu)
Scheme や Haskell などの関数型言語では，無限の長さのリストを自然に扱うことができる．例えば Haskell では
nat_from :: Int -> [Int]
nat_from x
= x : nat_from (x + 1)
という関数を定義すると，
nat_from 1
で [1, 2, 3, ...] という無限リストを生成できる．ちゃんと head (nat_from 1) で 1 が返るし，head (tail (nat_from 1)) では 2 が返る．無限ループに陥ったりはしない．同じ事を scheme でやろうとすると
(define-syntax lazy-cons
(syntax-rules ()
((_ x y) (cons x (delay y)))))
というマクロを用意し
(define nat-from
(lambda (x) (lazy-cons x (nat-from (+ x 1)))))
(nat-from 1)
と書くことになる．lazy-cons を使わなければならなかったのは，haskell が何もしなくても遅延評価なのに対し，scheme は delay/force 機構を用いなければ遅延評価されないからである．もしこれを
(define nat-from
(lambda (x) (cons x (nat-from (+ x 1)))))
としてしまうと，例えば (car (nat-from 1)) を評価しようとしても，先に (nat-from 1) を先に完全に構築しようとして無限ループに陥ってしまう．このように，無限リストを扱うためには遅延評価が必要になる．逆に，遅延評価（と再帰関数）が使えるなら，そのプログラミング言語では無限リストが扱える．
で，C++0x の情報を眺めていたら，lambda 式が追加されているのに気がついた（遅い）．lambda 式とは局所的に関数を生成する式のことで，例えば int 型同士の足し算を表す lambda 式は
[](int x, int y){ return x + y; }
のように書く．lambda 式の型を直接的に記述する手段は用意されていないが，std::function クラステンプレートを用いて
// #include <functional>
std::function<int(int,int)> plus
= [](int x, int y){ return x + y; }
のように捕捉できる．
ここで，lambda 式が表す関数は，関数を生成しただけでは実行されない．関数を実行するには，実際に引数を与えて
plus(1, 2)
のように呼んでやらなければならない．関数の生成を delay，呼び出しを force と考えると，これは scheme の delay/force 機構と同等である． C++ はもちろん再帰関数を使えるから，無限リストが作れるはずである．やってみる．
まず，scheme で言うところの cons セルを作る．通常のリストの cons セルは，具体的な値の入った car 部と，後続の cons セルである cdr 部のペアであるが，無限リストの場合は lazy-cons の定義にあるように，これは car 部と「cdr 部を生成する promise」のペアとなる．今，「cdr 部を生成する promise」は 「後続の cons セルを生成する lambda 式」に対応するから，cons セルの型は
template <typename T>
struct cell
{
T _car;
std::function<cell()> _cdr;
};
となるはずだ．とはいえ，これでは cell が値渡しになっていろいろと不自由なので， shared_ptr を用いて
template <typename T>
struct cell
{
T _car;
std::function<std::shared_ptr<cell>()> _cdr;
// コンストラクタ
cell(T car, std::function<std::shared_ptr<cell>()> cdr)
: _car(car), _cdr(cdr)
{}
};
とする（ついでにコンストラクタも定義した）．これを用ると，先ほどの無限リストを生成する関数は
std::shared_ptr<cell<int>>
nat_from(int x)
{
return std::shared_ptr<cell<int>>(
new cell<int>(x,
std::function<std::shared_ptr<cell<int>>()>(
[=](){ return nat_from(x + 1); })));
}
と書ける（lambda 式の [=] はおまじない）．おお，出来てしまった．試してみると
std::shared_ptr<cell<int>> ls = nat_from(1); std::cout << ls->_car << std::endl; // 1 std::cout << ls->_cdr()->_car << std::endl; // 2
となり，正しく動作している．ぶらぼー．
&trackback()
