|新しいページ|検索|ページ一覧|RSS|@ウィキご利用ガイド | 管理者にお問合せ
|ログイン|

無限リスト

    
※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

無限リスト

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

参考



コメント

name
comment


関連ページ



関連ブログ

正常にRSSを取得できませんでした。

プロフィール


tossy_squirrel



メニュー




更新履歴


取得中です。