「無限リスト」(2012/12/06 (木) 02:57:05) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*無限リスト
#right{last update: &update(format=Y/m/d (D))}
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 式が追加されているのに気がついた(遅い).C++ はもちろん再帰関数を使えるから,無限リストが作れるはずである.やってみる.
&trackback()
----
**参考
-[[Multi-threading Library for Standard C++ (Revision 1)>http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2497.html]]
----
**コメント
#comment(title_name=name,title_msg=comment)
----
**関連ページ
#related()
----
**関連ブログ
#blogsearch(C++0x)
*無限リスト
#right{last update: &update(format=Y/m/d (D))}
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()
----
**参考
-[[Multi-threading Library for Standard C++ (Revision 1)>http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2497.html]]
----
**コメント
#comment(title_name=name,title_msg=comment)
----
**関連ページ
#related()
----
**関連ブログ
#blogsearch(C++0x)
表示オプション
横に並べて表示:
変化行の前後のみ表示: