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

続続 無限リスト

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

続続 無限リスト

last update: 2012/12/11 (Tue )

前回,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

参考



コメント

name
comment


関連ページ



関連ブログ

  • 「C++0x」を含むブログが見つかりません。

プロフィール


tossy_squirrel



メニュー




更新履歴


取得中です。