「続続 無限リスト」(2012/12/11 (火) 22:46:34) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*続続 無限リスト
#right{last update: &update(format=Y/m/d (D))}
[[前回>続 無限リスト]]，C++0x の新機能である lambda 式を活用し，関数型言語における list を構築した．今回はまず，このクラスを使っていろいろなプログラムを書いてみる．まず，list の空判定と出力を実装する．
template <typename T>
class list
{
// 省略
// リストが空であるかどうか
bool
is_null() const { return !_cell; }
};
// 出力
// #include <ostream>
template <typename T>
std::ostream &
operator << (std::ostream & stream, list<T> const & xs)
{
return xs.is_null() ? stream << "()"
: stream << "(" << xs.car() << " , " << std::flush << xs.cdr() << ")";
}
次に，いくつかのリスト操作関数を実装する．
template <typename T>
class list
{
// 省略
// xs.take(n) で xs の先頭 n 要素を切り出す．
list<T>
take(unsigned int n) const
{
list xs = *this;
return n == 0 ? list()
: list(car(), [n, xs](){ return xs.cdr(), take(n - 1); });
}
// xs.zipWith(f, ys) で f(x, y) のリストを計算.
template <typename F, typename T2>
list<typename F::result_type>
zipWith(F const & f, list<T2> const & ys) const
{
list xs = *this;
return list<typename F::result_type>(
f(car(), ys.car()), [&f, xs, ys](){
return xs.cdr().zipWith(f, ys.cdr()); });
}
};
カンのいい Haskeller なら気付かれたかもしれないが，zipWith を選んだのは次のプログラムを書くためだ．
// in Haskell
fib = 1 : 1 : zipWith (+) fib (tail fib)
この1行でフィボナッチ数列が計算できる（それも線形時間で）．これを我らが C++ に翻訳すると
// #include <functional>
list<int> fib = list<int>(1, list<int>(1,
[&fib](){ return fib.zipWith(std::plus<int>(), fib.cdr()); }));
std::cout << fib.take(6) << std::endl;
// => (1, (1, (2, (3, (5, (8, ()))))))
すばらしい！が，喜ぶのはまだ早い． fib.take(30) あたりで計算が急激に遅くなってくる．Haskell と比べてどこに違いがあるのだろうか．
** グラフ簡約
フィボナッチプログラムの動作を追ってみよう．まず operator << 内で fib.car() され
(1, ...
が評価される．次に cdr() されて再び operator << に渡され car() されて
(1, (1, ...
となる．次の cdr() は遅延されているため，
(1, (1, { zipWith (+) fib fib.cdr() }
となり， operator << で car() されて
(1, (1, { fib.car() + fib.cdr().car() , ... }
=> (1, (1, ({ 1 + 1 }, ...
=> (1, (1, (2, ...
となる．さてこの次であるが，評価前は
(1, (1, (2, { zipWith (+) fib.cdr().car(), fib.cdr().cdr().car(), ... }
となっている．これを評価しようとすると，fib.cdr().car(), fib.cdr().cdr().car() などが計算される．
ところで，fib の 4 項目を計算するとき，fib の 3 項目以下は既に計算されているはずである．しかしながら，現在のリストの実装では，4 項目の計算時に 3 項目以下を再度計算してしまう．当然 5 項目を計算するために 4 項目を再度計算し，またそのためにみたび 3 項目を．．．と，計算量が爆発的に増えていく．これが計算が遅くなった原因である．
Haskell は遅延評価型の関数型言語であり，その評価戦略はグラフ簡約を用いている．どういうことかというと，一度計算したリストは，再度 cdr() されたとしても前の値をキャッシュしているのである．よって 5 項目の計算時には既に計算された 4 項目の値を用い，6 項目の計算時には既に計算された 5 項目の．．．と，計算量は爆発しない．
この仕組を我らのリストへ導入しよう．
&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))}
[[前回>続 無限リスト]]，C++0x の新機能である lambda 式を活用し，関数型言語における list を構築した．今回はまず，このクラスを使っていろいろなプログラムを書いてみる．まず，list の空判定と出力を実装する．
template <typename T>
class list
{
// 省略
// リストが空であるかどうか
bool
is_null() const { return !_cell; }
};
// 出力
// #include <ostream>
template <typename T>
std::ostream &
operator << (std::ostream & stream, list<T> const & xs)
{
return xs.is_null() ? stream << "()"
: stream << "(" << xs.car() << " , " << std::flush << xs.cdr() << ")";
}
次に，いくつかのリスト操作関数を実装する．
template <typename T>
class list
{
// 省略
// xs.take(n) で xs の先頭 n 要素を切り出す．
list<T>
take(unsigned int n) const
{
list xs = *this;
return n == 0 ? list()
: list(car(), [n, xs](){ return xs.cdr(), take(n - 1); });
}
// xs.zipWith(f, ys) で f(x, y) のリストを計算.
template <typename F, typename T2>
list<typename F::result_type>
zipWith(F const & f, list<T2> const & ys) const
{
list xs = *this;
return list<typename F::result_type>(
f(car(), ys.car()), [&f, xs, ys](){
return xs.cdr().zipWith(f, ys.cdr()); });
}
};
カンのいい Haskeller なら気付かれたかもしれないが，zipWith を選んだのは次のプログラムを書くためだ．
// in Haskell
fib = 1 : 1 : zipWith (+) fib (tail fib)
この1行でフィボナッチ数列が計算できる．これを我らが C++ に翻訳すると
// #include <functional>
list<int> fib = list<int>(1, list<int>(1,
[&fib](){ return fib.zipWith(std::plus<int>(), fib.cdr()); }));
std::cout << fib.take(6) << std::endl;
// => (1, (1, (2, (3, (5, (8, ()))))))
すばらしい！が，喜ぶのはまだ早い． fib.take(30) あたりで計算が急激に遅くなってくる．Haskell と比べてどこに違いがあるのだろうか．
** グラフ簡約
フィボナッチプログラムの動作を追ってみよう．まず operator << 内で fib.car() され
(1, ...
が評価される．次に cdr() されて再び operator << に渡され car() されて
(1, (1, ...
となる．次の cdr() は遅延されているため，
(1, (1, { zipWith (+) fib fib.cdr() }
となり， operator << で car() されて
(1, (1, { fib.car() + fib.cdr().car() , ... }
=> (1, (1, ({ 1 + 1 }, ...
=> (1, (1, (2, ...
となる．さてこの次であるが，評価前は
(1, (1, (2, { zipWith (+) fib.cdr().car(), fib.cdr().cdr().car(), ... }
となっている．これを評価しようとすると，fib.cdr().car(), fib.cdr().cdr().car() などが計算される．
ところで，fib の 4 項目を計算するとき，fib の 3 項目以下は既に計算されているはずである．しかしながら，現在のリストの実装では，4 項目の計算時に 3 項目以下を再度計算してしまう．当然 5 項目を計算するために 4 項目を再度計算し，またそのためにみたび 3 項目を．．．と，計算量が爆発的に増えていく．これが計算が遅くなった原因である．
Haskell は遅延評価型の関数型言語であり，その評価戦略はグラフ簡約を用いている．どういうことかというと，一度計算したリストは，再度 cdr() されたとしても前の値をキャッシュしているのである．よって 5 項目の計算時には既に計算された 4 項目の値を用い，6 項目の計算時には既に計算された 5 項目の．．．と，計算量は爆発しない．
この仕組を我らのリストへ導入しよう．
一度計算された値を保存して，次に呼び出されたときに利用すればよいのだから，
一度 cdr() されたとき，自動的に cell_impl_delayed から cell_impl_eager へ切り替えればよいということになる．しかし，以下のようなクラスを用いるともう少し汎用的な実装が可能だ．
template <typename S>
class promise
{
public:
typedef typename std::function<S>::result_type result_type;
private:
class cache_base
{
protected:
cache_base()
{
}
public:
virtual ~cache_base()
{
}
virtual typename std::function<S>::result_type
value() const = 0;
virtual bool
is_valued() const = 0;
};
class cache_impl_valued
: public cache_base
{
private:
typename std::function<S>::result_type _r;
public:
cache_impl_valued(typename std::function<S>::result_type const & r)
: cache_base(), _r(r)
{
}
typename std::function<S>::result_type
value() const { return _r; }
bool
is_valued() const { return true; }
};
class cache_impl_unvalued
: public cache_base
{
private:
std::function<S> _f;
public:
cache_impl_unvalued(std::function<S> const & f)
: cache_base(), _f(f)
{
}
typename std::function<S>::result_type
value() const { return _f(); }
bool
is_valued() const { return false; }
};
mutable std::shared_ptr<cache_base> _cache;
public:
promise(std::function<S> const & f)
: _cache(new cache_impl_unvalued(f))
{
}
typename std::function<S>::result_type
operator () () const
{
if (_cache->is_valued()) {
return _cache->value();
}
else {
typename std::function<S>::result_type r = _cache->value();
_cache.reset(new cache_impl_valued(r));
return r;
}
}
};
このクラステンプレートは std::function<T()> と同様に振る舞うが，一度 operator () が呼ばれると結果の値をキャッシュする．そして再度 operator () が呼ばれた時にキャッシュされた値を利用する．次にリストの実装を一箇所だけ変更する．
struct cell_impl_delayed
: public cell_base
{
promise<std::shared_ptr<cell_base>()> _cdr;
// std::function<std::shared_ptr<cell_base>()> _cdr;
cell_impl_delayed(T const & car, std::function<std::shared_ptr<cell_base>()> const & cdr)
: cell_base(car), _cdr(cdr)
{
}
std::shared_ptr<cell_base>
cdr() const { return _cdr(); }
};
これによって，次のプログラム
list<int> fib = list<int>(1, list<int>(1,
[&fib](){ return fib.zipWith(std::plus<int>(), fib.cdr()); }));
は線形時間で動作する．さらに
T
car() { return _cell->car(); }
なるメンバ関数を定義しておくと，
std::cout << fib.take(6) << std::endl;
// => (1, (1, (2, (3, (5, (8, ()))))))
fib.cdr().cdr().cdr().car() = 1;
std::cout << fib.take(6) << std::endl;
// => (1, (1, (2, (1, (5, (8, ()))))))
なんてことが可能になったりする．
さて，同じプログラムを scheme と haskell で実装してみるとわかるが，関数型言語が本領を発揮するには，「よくある」汎用アルゴリズムを用意したときである．「よくある」アルゴリズムとしては，map, zip, filter, foldl, scanl, foldr, scanr 等々，様々に存在する．このあたりは，Haskell を参考になんなりと実装しておけばよい．例えば map であれば
template <typename F>
list<typename F::result_type>
map(F const & f) const
{
list xs = *this;
return list<typename F::result_type>(
f(car()), [&f, xs](){ return xs.cdr().map(f); });
}
のようになる．map ができたら，例えば
std::function<int(int)> inc = [](int x){ return x + 1; };
list<int> seq = list<int>(1, std::function<list<int>()>(
[&seq, &inc](){ return seq.map(inc); }));
std::cout << seq.take(10) << std::endl;
// => (1, (2, (3, (4, (5, (6, (7, (8, (9, 10, ())))))))))
のように等差数列が書けたりする．
&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)
表示オプション
横に並べて表示：
変化行の前後のみ表示：
