1

範囲でいくつかの関数プログラミング操作を可能にするライブラリを作成しています。範囲は、STL コンテナーの一般化です。私の質問は、空の範囲の折りたたみの結果はどうあるべきですか?

auto r  = range(4);    // lazy numeric range {0,1,2,3}
auto r0 = range(0);    // empty range {}
vector<string> vs  {"a", "bb"};
vector<string> vs0 {};

// this is obvious and implemented part    

cout <<  (r  || add);  // 6,  || - folding op
cout <<  (r0 || add);  // 0
cout <<  (vs || add);  // "abb"
cout <<  (vs0|| add);  // ""

cout <<  (r  || mul);  // 0
cout <<  (r0 || mul);  // 1

cout <<  (r  || max);  // 3

//  What result of these should be?

cout <<  (r0 || div);   // ???
cout <<  (r0 || sub);   // ???
cout <<  (r0 || max);   // -∞ ???
cout <<  (r0 || min);   // +∞ ???
cout <<  (r0 || ???);   // result of arbitrary op?

編集 - 回答

http://en.wikipedia.org/wiki/Identity_element

4

1 に答える 1

2

あなたの「フォルダー」は、バイナリ関数が添付され、おそらく初期値を持つ、いくつかのテンプレートのインスタンスであると思います。

伝統的に、フォールドは、呼び出すものがなくなるまで、上記のバイナリ関数を (最初に、最初に)、次に (古い値に、次に) 再帰的に呼び出すこととして定義されます。

減算と除算が期待どおりに機能するような初期値はありません (fold({1,2}) が 1/2 になるような)。

したがって、減算と除算の「フォルダー」は、「逆数の合計」または「逆数の積」のいずれかです (つまり、fold(r) = 1/fold(r)、および fold(r) = -fold(r))。かなり退屈です)、またはそれらは空のコンテナーでは機能しない根本的に異なるものです。

max と min は、特定のタイプの最高値と最低値を明確に生成する必要があります。または、空のコンテナーでは意味をなさない 2 番目のタイプのフォルダーにする必要があります。

「動作しない」ということで、例外をスローするか、何かを返すことができますboost::optional<T>。つまり、空のリストでは、何も返しません。

フォルダ タイプは、指定されたタイプの初期値を見つける関数を取ることができます。これは、特性テンプレート クラスまたはフリー関数 ( に似ていますstd::begin) に解決される必要があります。

...

編集：以下のコメントから、回答の改善。

ここでの本当のトリックは、減算と除算に左手の恒等式がないことですが、右手の恒等式はあります!

右手の同一性のみを持つ操作は右折として表現し、左手の同一性のみを持つ操作は左折として表現する必要があります (別名、foldr および foldl)。

つまり、2 項演算の{a,b,c}恒等式を使用してリストの折り畳みを表現する自然な方法は次のとおりです。id*op*

( (id *op* a) *op* b ) *op c

しかし、左側の恒等式がない操作では、これは機能しません。

ただし、フォールド利き手を逆にすると、次のようになります。

a *op* (b *op* (c *op* id))

これは、右手のアイデンティティを持っている限り機能します。

divこれはandにとって重要ですsub--divの右単位は 1 で、sub右単位は 0 ですが、どちらも左単位はありません。( for all という要素はありません。efor all 、つまり 0という要素はあります)。e-x = xxex-e = xx

同じことがべき乗にも当てはまります (右辺単位は1ですが、左辺単位はありません)。

これは、何をすべきかについての素朴な期待とはまだ一致していませfold divん。長さ 2 のリストでは機能しますが、長さ 3 のリストでは直観的でないことが起こります。しかし、少なくとも数学的には正しいです。:)

于 2012-12-12T19:31:40.190 に答える