squirrel_code @ ウィキ
続 無限リスト
最終更新：
squirrel_code
-
view
続 無限リスト
last update: 2012/12/08 (Sat)
前回，C++0x を用いて基本的な無限リストを作成した．とはいえ，目につく問題も残っていた．例えばリストを扱うために常に shared_ptr を経由しなければならなかったり，リストの 2 番目を参照するために ls->cdr()->car といった不自然なメソッド呼び出しをする必要があったりした．これを改善しよう．
まず，常に shared_ptr となるのを防ぐには，cons セル全体をラッパクラスで覆えばよい．例えば以下のようになる．
template<typename T>
class list
{
struct cell
{
T _car;
std::function<std::shared_ptr<cell>()> _cdr;
cell(T const & car, std::function<std::shared_ptr<cell>()> const & cdr)
: _car(car), _cdr(cdr)
{}
};
std::shared_ptr<cell> _cell;
};
std::list と名前が衝突する？ そんなことは using namespace std する奴が悪いのだ（おい）それよりも問題は，この list をどうやって構築するかである．前回は cell 構造体そのものを lambda 式を用いて直接構築した．しかし今回は cell 構造体は private なので外部からは隠蔽されている．なので nat_from で「std::shared_ptr<cell> を返す lambda 式」を直接生成できない．
そこで，ユーザ側では 「list を返す lambda 式」を定義してもらって，それを「std::shared_ptr<cell> を返す lambda 式」に変換してやる必要がある．この変換をコンストラクタとして実装してやればよい．
ついでに，C++0x らしく cell 構造体はコピー・代入禁止とし，さらに car と cdr へのアクセサを実装しておく．
template <typename T>
class list
{
struct cell
{
T car;
std::function<std::shared_ptr<cell>()> cdr;
cell(T const & car, std::function<std::shared_ptr<cell>()> const & cdr)
: car(car), cdr(cdr)
{
}
cell(cell const &) = delete;
cell
operator = (cell const &) = delete;
};
std::shared_ptr<cell> _cell;
public:
list()
{
}
private:
list(std::shared_ptr<cell> const & cell)
: _cell(cell)
{
}
public:
list(T const & car, std::function<list<T>()> const & cdr)
: _cell(new cell(car, [cdr]() { return cdr()._cell; }))
{
}
T
car() const { return _cell->car; }
list
cdr() const { return list(_cell->cdr()); }
};
これを用いて nat_from を実装すると
list<int>
nat_from(int k)
{
return list<int>(k, [k]() { return nat_from(k + 1); });
}
おおー，ずっと自然になった．
有限リスト
これで自由自在に無限リストを使えるようになったであろうか．いや，まだ気が早い．例えば nat_from(1) で 1 から始まる増加列を生成できたとして，これの先頭に 0 を加えたい場合どうすればよいだろう．すでにある list を返す promise を改めて生成し，list 構築なんてめんどくさい．というか，有限だろうが無限だろうが，生成する方法は異なっても使うときは同じように使いたいのだ．これを実現しよう．
まず，有限リスト用の cons セルを定義する．これを無限リスト用の cons セルと混ぜて使いたいから，同じ基底クラスを持つ派生クラスとして定義すればよいだろう．ここで car 部は共通だから基底クラスが持てばよい．cdr 部は有限リストなら shared_ptr<cell> を，無限リストなら function<shared_ptr<cell>()> を保持し，アクセスされたら shared_ptr<cell> を返すようなアクセサを用意する．
template <typename T>
class list
{
class cell_base
{
T _car;
public:
cell_base(T const & car)
: _car(car)
{
}
cell_base(cell_base const &) = delete;
virtual ~cell_base()
{
}
cell_base
operator = (cell_base const &) = delete;
T const &
car() const { return _car; }
virtual std::shared_ptr<cell_base>
cdr() const = 0;
};
struct cell_impl_eager
: public cell_base
{
std::shared_ptr<cell_base> _cdr;
cell_impl_eager(T const & car, std::shared_ptr<cell_base> const & cdr)
: cell_base(car), _cdr(cdr)
{
}
std::shared_ptr<cell_base>
cdr() const { return _cdr; }
};
struct cell_impl_delayed
: public cell_base
{
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(); }
};
std::shared_ptr<cell_base> _cell;
public:
list()
{
}
private:
list(std::shared_ptr<cell_base> const & cell)
: _cell(cell)
{
}
public:
list(T const & car, list<T> const & cdr)
: _cell(new cell_impl_eager(car, cdr._cell))
{
}
list(T const & car, std::function<list<T>()> const & cdr)
: _cell(new cell_impl_delayed(car, [cdr]() { return cdr()._cell; }))
{
}
T const &
car() const { return _cell->car(); }
list
cdr() const { return list(_cell->cdr()); }
};
試してみる．
list<int> ls = nat_from(1); ls = list<int>(0, ls); std::cout << ls.car() << std::endl; // 0 std::cout << ls.cdr().car() << std::endl; // 1 std::cout << ls.cdr().cdr().car() << std::endl; // 2
できちまったぜ．
&trackback()
