「続 無限リスト」の編集履歴（バックアップ）一覧に戻る

続 無限リスト - (2012/12/06 (木) 22:27:25) のソース

*続 無限リスト
#right{last update: &update(format=Y/m/d (D))}

[[前回>無限リスト]]，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 式」に変換してやる必要がある．この変換関数は scheme でいう cons そのものだろう．これはコンストラクタで実装できる．

ついでに，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> cell)
        : _cell(cell)
     {
     }
 
     public:
     list(T const & car, std::function<list<T>()> 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); });
 }
おおー，ずっと自然になった．

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