「続 無限リスト」の編集履歴（バックアップ）一覧はこちら

「続 無限リスト」(2012/12/08 (土) 05:27:51) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*続 無限リスト
#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 式」に変換してやる必要がある．この変換をコンストラクタとして実装してやればよい．

ついでに，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 部は共通だから基底クラスが持てばよい．ついでに，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; }
 
         T &
         car() { 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(); }
 
     T &
     car() { 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
 ls.cdr().car() = 5;
 std::cout << ls.car() << std::endl; // 0
 std::cout << ls.cdr().car() << std::endl; // 5
 std::cout << ls.cdr().cdr().car() << std::endl; // 2
できちまったぜ．

当然ながら car 部への代入がうまくいくのは，有限リスト部か，無限リストの先頭要素に限られる．（なぜなら ls の段階では無限リストの 2 番目以降はまだ評価されてないからね）まぎらわしいので，これは無くてもよいかもしれん．この手の機能は zipper とか使えば実現できるし．．．

&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 を用いて基本的な無限リストを作成した．とはいえ，目につく問題も残っていた．例えばリストを扱うために常に 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()
----
**参考
-[[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)