続続 無限リスト - squirrel_code @ ウィキ

続続 無限リスト

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()

---

参考

• Multi-threading Library for Standard C++ (Revision 1)

---

コメント

---

関連ページ

• トップページ

---

関連ブログ

#blogsearch