64

Boost メーリングリストで、タプルのようなエンティティを作成する次の巧妙なトリックが @LouisDionne によって最近投稿されました。

#include <iostream>

auto list = [](auto ...xs) { 
    return [=](auto access) { return access(xs...); }; 
}; 

auto length = [](auto xs) { 
    return xs([](auto ...z) { return sizeof...(z); }); 
};

int main()
{
    std::cout << length(list(1, '2', "3")); // 3    
}

ライブの例

巧妙なのはlist、ラムダが可変引数リストを入力として取り、入力に作用する別のラムダを取る出力としてラムダを返すことです。同様に、lengthリストのようなエンティティを受け取るラムダであり、リストの元の入力パラメータに可変引数sizeof...演算子を提供します。sizeof...に渡すことができるように、演算子はラムダ内にラップされますlist

質問: このタプル作成イディオムの名前はありますか? おそらく、高階関数がより一般的に使用される関数型プログラミング言語からのものでしょう。

4

3 に答える 3

31

これはモナドのようなもの、特に継続モナドと同じ精神の何かの微妙な実装だと思います。

モナドは、計算の異なるステップ間の状態をシミュレートするために使用される関数型プログラミング構造です (関数型言語はステートレスであることを思い出してください)。
モナドが行うことは、さまざまな関数を連鎖させ、各ステップが計算の現在の状態を認識する「計算パイプライン」を作成することです。

モナドには 2 つの主要な柱があります。

  • 値を受け取り、それを Monad 対応の形式で返す return 関数。
  • Monad 対応の値 (前のパイプライン ステップから) を受け取り、それを元の from にアンラップして値を次のステップに渡すバインド関数。

ウィキペディアには、モナドに関する非常に良い例と説明があります。

与えられた C++14 コードを書き直してみましょう。

auto list = []( auto... xs ) 
{ 
    return [=]( auto access ) { return access(xs...); };
};

ここでモナドの機能を識別していると思いますreturn。値を受け取り、モナドの方法で返します。具体的には、この戻り値は、「タプル」カテゴリから可変個パック カテゴリに移動するファンクタ (数学的な意味では、C++ ファンクタではありません) を返します。

auto pack_size = [](auto... xs ) { return sizeof...(xs); };

pack_sizeは単なる正常な機能です。何らかの作業を行うためにパイプラインで使用されます。

auto bind = []( auto xs , auto op ) 
{
    return xs(op);
};

そして、モナド演算子にlength近い何かの非ジェネリック バージョンにすぎません。これは、前のパイプライン ステップからモナド値を取得し、それを指定された関数 (実際に作業を行う関数) にバイパスする演算子です。bindその機能は、この計算ステップによって実行される機能です。

最後に、呼び出しは次のように書き換えることができます。

auto result = bind(list(1,'2',"3"), pack_size);

では、このタプル作成イディオムの名前は何ですか? 正確にはモナドではないので、これは「モナドのようなタプル」と呼ぶことができると思いますが、タプルの表現と展開は同様の方法で機能し、Haskell の継続モナドのままです。

編集:もっと楽しい

面白い C++ プログラミングの震えのために、私はこのモナドのようなものを探求してきました。ここでいくつかの例を見つけることができます。

于 2014-08-16T11:52:01.650 に答える
19

私はこの慣用句をtuple-continuator、またはより一般的にはmonadic-continuatorと呼びます。これは間違いなく継続モナドのインスタンスです。C++ プログラマー向けの継続モナドの優れた紹介は、こちらです。本質的に、list上記のラムダは値 (可変引数のパラメーター パック) を取り、単純な「継続子」 (内部クロージャー) を返します。このコンティニュエータは、callable ( と呼ばれるaccess) が与えられると、パラメータ パックをそれに渡し、その callable が返すものを返します。

FPComplete ブログ投稿から借りると、コンティニュエーターは多かれ少なかれ次のようになります。

template<class R, class A>
struct Continuator {
    virtual ~Continuator() {}
    virtual R andThen(function<R(A)> access) = 0;
};

上記Continuatorは抽象的であり、実装を提供しません。だから、ここに簡単なものがあります。

template<class R, class A>
struct SimpleContinuator : Continuator<R, A> {
    SimpleContinuator (A x) : _x(x) {}
    R andThen(function<R(A)> access) {
        return access(_x);
    }
    A _x;
};

は typeのSimpleContinuator値を 1 つ受け取り、が呼び出されたときにAそれを に渡します。上記のラムダは本質的に同じです。より一般的です。単一の値の代わりに、内側のクロージャーはパラメーター パックをキャプチャし、それを関数に渡します。きちんとした!accessandThenlistaccess

うまくいけば、それが継続者であることの意味を説明しています。しかし、モナドであるとはどういう意味ですか? 写真を使ったわかりやすい紹介です。

listラムダもリストモナドであり、継続モナドとして実装されていると思います。継続モナドはすべてのモナドの母であることに注意してください。つまり、継続モナドを持つ任意のモナドを実装できます。もちろん、リストモナドは手の届かないものではありません。

parameter-pack は非常に自然に「リスト」(多くの場合異種の型) であるため、リスト/シーケンス モナドのように機能することは理にかなっています。上記のlistラムダは、C++ パラメーター パックをモナド構造に変換する非常に興味深い方法です。したがって、操作を次々と連鎖させることができます。

ただし、上記のlengthラムダはモナドを壊し、内部のネストされたラムダは単純に整数を返すため、少しがっかりします。以下に示すように、長さ「ゲッター」を記述するより良い方法が間違いなくあります。

- - ファンクタ - -

リスト lambda がモナドであると言う前に、それがファンクターであることを示さなければなりません。つまり、list には fmap を記述する必要があります。

上記のラムダ リストは、パラメーター パックからのファンクターの作成者として機能しますreturn。その作成されたファンクターはパラメーターパックをそれ自体で保持し(キャプチャー)、可変数の引数を受け入れる呼び出し可能オブジェクトを指定すると、それに「アクセス」できます。callable は EXACTLY-ONCE と呼ばれることに注意してください。

そのようなファンクターの fmap を書きましょう。

auto fmap = [](auto func) { 
    return [=](auto ...z) { return list(func(z)...); };
};

func の型は (a -> b) でなければなりません。つまり、C++ で言えば、

template <class a, class b>
b func(a);

fmap の型はつまりfmap: (a -> b) -> list[a] -> list[b]、C++ で言えば、

template <class a, class b, class Func>
list<b> fmap(Func, list<a>);

つまり、fmap は a のリストを b のリストにマップするだけです。

今、あなたはすることができます

auto twice = [](auto i) { return 2*i; };
auto print = [](auto i) { std::cout << i << " "; return i;};
list(1, 2, 3, 4)
    (fmap(twice))
    (fmap(print)); // prints 2 4 6 8 on clang (g++ in reverse)

したがって、それはファンクターです。

----モナド----

flatmapでは、 (aka bind, selectmany)を書いてみましょう。

フラットマップのタイプはflatmap: (a -> list[b]) -> list[a] -> list[b].

つまり、a を b のリストと a のリストにマップする関数を指定すると、flatmap は b のリストを返します。本質的に、それは list-of-a から各要素を取得し、それに対して func を呼び出し、(空の可能性がある) list-of-b を 1 つずつ受け取り、すべての list-of-b を連結し、最終的なリストを返します。 -of-b。

リストの flatmap の実装を次に示します。

auto concat = [](auto l1, auto l2) {
    auto access1 = [=](auto... p) {
      auto access2 = [=](auto... q) {
        return list(p..., q...);
      };
      return l2(access2);
    };
    return l1(access1);
};

template <class Func>
auto flatten(Func)
{
  return list(); 
}

template <class Func, class A>
auto flatten(Func f, A a)
{
  return f(a); 
}

template <class Func, class A, class... B>
auto flatten(Func f, A a, B... b)
{
  return concat(f(a), flatten(f, b...));
}

auto flatmap = [](auto func) {
  return [func](auto... a) { return flatten(func, a...); };
};

リストを使って多くの強力なことができるようになりました。例えば、

auto pair  = [](auto i) { return list(-i, i); };
auto count = [](auto... a) { return list(sizeof...(a)); };
list(10, 20, 30)
    (flatmap(pair))
    (count)
    (fmap(print)); // prints 6.

count 関数は、単一要素のリストを返すため、モナドを維持する操作です。本当に長さを取得したい (リストにラップされていない) 場合は、モナド チェーンを終了し、次のように値を取得する必要があります。

auto len = [](auto ...z) { return sizeof...(z); }; 
std::cout << list(10, 20, 30)
                 (flatmap(pair))
                 (len);

正しく行われた場合、コレクション パイプラインパターン (例: filterreduce) を C++ パラメーター パックに適用できるようになりました。甘い!

----モナド法則----

モナドが 3 つのモナド法則listをすべて満たしていることを確認しましょう。

auto to_vector = [](auto... a) { return std::vector<int> { a... }; };

auto M = list(11);
std::cout << "Monad law (left identity)\n";
assert(M(flatmap(pair))(to_vector) == pair(11)(to_vector));

std::cout << "Monad law (right identity)\n";
assert(M(flatmap(list))(to_vector) == M(to_vector));

std::cout << "Monad law (associativity)\n";
assert(M(flatmap(pair))(flatmap(pair))(to_vector) == 
       M(flatmap([=](auto x) { return pair(x)(flatmap(pair)); }))(to_vector));

すべてのアサートが満たされます。

----収集パイプライン----

上記の 'list' ラムダは確かにモナドであり、ことわざの 'list-monad' の特徴を共有していますが、これは非常に不快です。特に、(aka )などの一般的なコレクション パイプラインコンビネータの動作は、一般的な期待を満たしていないためです。filterwhere

その理由は、C++ ラムダの仕組みにあります。各ラムダ式は、一意の型の関数オブジェクトを生成します。したがって、list(1,2,3)は何も関係のない型とlist(1)空のリスト (この場合は ) を生成しますlist()

C++ では関数が 2 つの異なる型を返すことができないため、単純な実装はwhereコンパイルに失敗します。

auto where_broken = [](auto func) {
  return flatmap([func](auto i) { 
      return func(i)? list(i) : list(); // broken :-(
  }); 
};

上記の実装では、 func はブール値を返します。各要素の true または false を示す述語です。?: 演算子はコンパイルされません。

したがって、別のトリックを使用して、コレクション パイプラインを継続できるようにすることができます。要素を実際にフィルタリングするのではなく、単にそのようにフラグを立てるだけであり、それが不快な理由です。

auto where_unpleasant = [](auto func) {
  return [=](auto... i) { 
      return list(std::make_pair(func(i), i)...);
  }; 
};

where_unpleasant仕事を成し遂げますが、不愉快です...

たとえば、これはネガティブな要素をフィルタリングする方法です。

auto positive = [](auto i) { return i >= 0; };
auto pair_print = [](auto pair) { 
  if(pair.first) 
     std::cout << pair.second << " "; 
  return pair; 
};
list(10, 20)
    (flatmap(pair))
    (where_unpleasant(positive))
    (fmap(pair_print)); // prints 10 and 20 in some order

----異種タプル----

これまでの議論は同種タプルについてでした。これを真のタプルに一般化しましょう。ただしfmap、、、コールバック ラムダは 1 つしか取りませんflatmapwhereそれぞれが 1 つの型で動作する複数のラムダを提供するために、それらをオーバーロードできます。例えば、

template <class A, class... B>
struct overload : overload<A>, overload<B...> {
  overload(A a, B... b) 
      : overload<A>(a), overload<B...>(b...) 
  {}  
  using overload<A>::operator ();
  using overload<B...>::operator ();
};

template <class A>
struct overload<A> : A{
  overload(A a) 
      : A(a) {} 
  using A::operator();
};

template <class... F>
auto make_overload(F... f) {
  return overload<F...>(f...);   
}

auto test = 
   make_overload([](int i) { std::cout << "int = " << i << std::endl; },
                 [](double d) { std::cout << "double = " << d << std::endl; });
test(10); // int 
test(9.99); // double    

オーバーロードされたラムダ手法を使用して、異種のタプル継続子を処理しましょう。

auto int_or_string = 
        make_overload([](int i) { return 5*i; },
                      [](std::string s) { return s+s; });
    list(10, "20")
        (fmap(int_or_string))
        (fmap(print)); // prints 2020 and 50 in some order

最後に、実際の例

于 2014-08-16T18:31:18.353 に答える
3

これは継続渡しスタイルの形式のように見えます。

CPS の大まかな考え方は次のとおりです。関数 (たとえばf) に何らかの値を返す代わりに、別の引数 ( continuationfと呼ばれる関数) に渡します。次に、戻る代わりに戻り値を使用してこの継続を呼び出します。例を見てみましょう:f

int f (int x) { return x + 42; }

になる

void f (int x, auto cont) { cont (x + 42); }

呼び出しはテール コールであり、ジャンプに最適化できます (これが、Scheme などの一部の言語で TCO が義務付けられている理由です。Scheme では、セマンティクスが CPS への何らかの形式の変換に依存しています)。

もう一つの例:

void get_int (auto cont) { cont (10); }
void print_int (int x) { printf ("%d", x), }

get_int (std::bind (f, _1, print_int))これで、54 を印刷することができます。すべての継続呼び出しは常に末尾呼び出しであることに注意してください (への呼び出しprintfも継続呼び出しです)。

よく知られている例は、非同期コールバック (たとえば、javascript での AJAX 呼び出し) です。並行して実行されるルーチンに継続を渡します。

上記の例のように、継続は構成できます (興味がある場合は、モナドを形成します)。実際、(関数型の) プログラムを完全に CPS に変換して、すべての呼び出しを末尾呼び出しにすることができます (その場合、プログラムを実行するためにスタックは必要ありません!)

于 2014-09-02T20:13:56.403 に答える