読者です 読者をやめる 読者になる 読者になる

C++で、Ruby、LINQライクなコンテナの操作とモナド内包表記のライブラリを作った(紹介編)

C++11用の、RubyLINQライクなコンテナの操作、および(モナド)内包表記を提供するライブラリ「Amulet」を作りました(現在も開発中です)。

GitHubリポジトリはこちらです: https://github.com/iofg2100/amulet

なお、Boostが必要になります。

なぜ作ったか?

このライブラリの様に、C++RubyLINQライクな(関数型ライクな)コンテナ処理を実現する既存のライブラリは幾つもあります。

今回このライブラリを開発した理由は

  • 普通のメソッドとして書きたい
    • 拡張メソッド形式だと、using namespaceしない限りすべてのメソッドにnamespaceを書かなければいけなくなったり、メソッドと他の識別子が衝突して面倒だったりと不便
  • 内包表記のために、クラスはモナドであってほしい
  • map, filterなどで返された値はrange-based forでも使えるようにしたい

これらの条件を満たすものが見つからなったからです。また、単純に、自分でこのようなライブラリを作るのが面白そうだったからでもあります。

コンテナ用の便利なメソッド

(ここでは簡単のためにメンバ関数をメソッドと呼ぶことにします)

Amulet::RangeExtensionは、指定した型(std::vectorなどのコンテナ型)にRubyLINQのような便利なコンテナ操作用メソッドを追加するテンプレートクラスです。(メソッド名は、RubyやScalaを意識しています)

指定した型を継承して、C++11のInheriting constructorでコンストラクタも同時に継承すると同時に、 新たなメソッドを定義することで、既存の型に様々なコンテナ処理メソッドを追加する仕組みになっています。

これによって追加されたメソッドを使うことによって、メソッドチェーンでコンテナを変形していくような直感的な処理をできるようにしました。

ちなみに、mapやfilterなど、新たな変形されたコンテナを返すメソッドは、遅延評価されるようになっています(それらのコンテナの要素の値は実際に参照された時に初めて評価されます。) 内部的には、Boost.Iteratorで提供される遅延評価のイテレータを使用しています。 ちなみに、内部で元のコンテナをムーブあるいはコピーしているので、元のコンテナが削除されても問題はありません。

#include <amulet/range_extension.hh>

RangeExtension<std::vector<int>> xs = {1,2,3};

// それぞれの値に与えられた関数を適用して、得られた値のコンテナを得る
xs.map([](int x){
  return x * 2;
}); // => {2,4,6}

// 条件を満たす値のみのコンテナを得る
xs.filter([](int x){
  return x % 2 == 0;
}); // => {2}

// 逆順のコンテナを得る
xs.reverse(); // => {3,2,1}

// 和を計算
xs.foldLeft(0, [](int sum, int x){
  return sum + x;
}); // => 6

// それぞれの値に与えられた関数を適用して、得られた値の各要素を集めて、コンテナを得る
xs.flatMap([](int x){
  return RangeExtension<std::vector<int>>{x, x};
}); // => {1,1,2,2,3,3}

// それぞれの値にindexを付加し、std::pairにする
xs.withIndex(); // => {{0,1},{1,2},{2,3}}

既存のコンテナの値をラップ

Amulet::extend関数を使うことで、既存のコンテナをラップして、RangeExtensionで追加されるメソッドを使えるようにすることもできます。

#include <amulet/range_extension.hh>

std::vector<int> vec = {1,2,3};
auto twices = Amulet.extend(vec).map([](int x){
  return x * 2;
});

整数のRange

Amulet::intRangeは、RangeExtensionのメソッドが使える整数値のRangeを返します。

#include <amulet/int_range.hh>

auto fizzbuzz = Amulet::intRange(0, 100).map([](int x)->std::string{
  if (x % 15 == 0)
    return "fizzbuzz";
  else if (x % 3 == 0)
    return "fizz";
  else if (x % 5 == 0)
    return "buzz";
  else
    return std::to_string(x);
});

std::copy(fizzbuzz.begin(), fizzbuzz.end(), std::ostream_iterator<std::string>(std::cout, " "));
std::cout << std::endl;

LINQクエリ式っぽい内包表記(モナド内包表記)

プリプロセッサマクロを使って(乱用して)、LINQクエリ式・Scalaのfor内包表記・Haskellのdo記法のような内包表記を実現してみました(個人的に作っていて最も面白かった部分です)。 コンテナ(RangeExtension)から新たなコンテナを構築する際などに使用することができます。 これを"Query macro"と呼んでいます。

ちなみに、この内包表記は、RangeExtensionだけでなくモナド一般に対して使えるように設計されています(モナド内包表記)。

#include <amulet/short_query_macro.hh>
#include <amulet/range_extension.hh>

template <typename T>
using ExVector = Amulet::RangeExtension<std::vector<T>>;

auto xs = ExVector<int>{1,2};
auto ys = ExVector<int>{3,4};

auto product = _do(
  _from(x, xs),
  _from(y, ys),
  _select(std::make_pair(x, y))
); // => {{1,3},{1,4},{2,3},{2,4}}

ExVector<std::pair<std::string, int>> prices = {
  {"orange", 50},
  {"apple", 100},
  {"banana", 150},
  {"carrot",90}};

// 内包表記版
auto fruitPrices1 = _do(
  _from(pair, prices),
  _where(pair.first != "carrot"),
  _select(pair.second)
);

// メソッドチェーン版
auto fruitsPrices2 = prices.filter([](const std::pair<std::string, int> &pair){
  return pair.first != "carrot";
}).seconds();

Option型

Amulet::Optionは、無効かもしれない値を格納するコンテナのような値です(boost::optionalなどと同じ)。 boost::optionalはポインタに似せた作りになっている一方、Amulet::Optionはコンテナに似せた作りになっているのが特徴です。 (イテレータもあるのでrange-based forでも使えます。ただしRangeExtensionではありません。)

全体的には、ScalaのOptionを意識した設計になっています。

Optionも、RangeExtensionと同様に、内包表記を使用することができます(モナドになっています)。 この内包表記を使うことで、シンプルにOptionの合成(元のOptionが無効であれば、できるOptionも無効にするといった)を行うことができます。

#include <amulet/short_query_macro.hh>
#include <amulet/option.hh>

auto divide = [](int x, int y) -> Amulet::Option<int>{
  if (y)
    return Amulet::some(x / y);  // 成功
  else
    return Amulet::none;  // 失敗、無効値を返す
};
auto a = Amulet::some(0);
auto b = Amulet::some(1);

auto divided = _do(
  _from(x, b),
  _from(y, a),
  divide(x, y)
); // divideが失敗するので無効値を返す

auto added1 = _do(
  _from(x, a),
  _from(y, b),
  _select(x + y)
); // Amulet::Optional<int>(1)

auto added2 = _do(
  _from(x, a),
  _from(y, divided),
  _select(x + y)
); // dividedが無効値なのでこれも無効値を返す

モナド

モナドMonad)とは、Haskell、Scalaなのでよく使われているデザインパターンのようなものです(詳細の説明は詳しい人に譲ります)。 このライブラリは、内包表記を書けるようにするための仕組みとしてモナドを使っています。

このライブラリでは、クラスがモナドであること(Monadコンセプト)を次のように定義しています:

  • value_type型を持つ
  • template <typename F> flatMap(F f) メソッドを持つ
  • template <typename T> fromValue(const T &vaue) staticメソッドを持つ

これらの条件を満たすクラスのインスタンスは、内包表記内で使用できるようになります。すなわち、内包表記のマクロはこれらのメンバの組み合わせに展開されます(ただし、_where句を使う際にはfilterメソッドが必要になります)。

RangeExtensionやOptionは、これらの条件を満たしてるので、内包表記で使えるようになっているのです。

問題点:コンテナのコピーコスト

map, filterなどのメソッドは、*thisがlvalueだった場合に*thisのコピーを内部に持つ遅延評価コンテナを返す設計になっています(rvalueであればムーブします)。 このコピーコストを抑えるためには、std::moveを使うことができます。

auto mapped = std::move(xs).map([](int x){
  return x * 2;
}); // => {2,4,6}, xsは無効になる(mappedに内部的に格納される)

ただし、ムーブしたくない場合(xsがconstである、xsをあとで使いたい等の場合)は、どうしてもコピーが発生してしまいます。

また、内包表記内ではコピーキャプチャのラムダ式を生成しているので、ここでもコンテナのコピーコストが発生するという問題があります。(遅延評価を行うため、参照キャプチャを行うとすでに存在しない値を参照するなどの問題が発生してしまいます。変数ごとにキャプチャの方法を選択できるようにすることもできますが、非常に複雑になってしまいます。)

なお、Qtのコンテナ(QList、QVector、…)などのコピーオンライトなコンテナではこういった問題は発生しません。

これからやりたいこと

RangeExtensionにはまだまだメソッドが足りないので、もっと追加して実用的で便利なライブラリを目指したいです。

また、Amuletではモナドが使えるので、さらにモナドを使った機能(Parsecライクなパーサライブラリなど)を追加していきたいです。