foldr を書く
foldr とは次のような関数です。
foldr :: (a -> b -> b) -> b -> [a] -> b foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs)
これを C++ で書いてみます (foldr' を書きます)。
仕様は accumulate のものを copy and paste (+ modify) して以下のようにしましょう。ちなみに accumulate は
template <class InputIterator, class T, class BinaryOperation> T foldr(InputIterator first, InputIterator last, T init, BinaryOperation binary_op);
Effects: Computes its result by initializing the accumulator acc with the initial value init and then modifies it with acc = binary_op(*i, acc) for every iterator i in the range [first,last) in reverse order.
Requires: T shall meet the requirements of CopyConstructible and CopyAssignable types. In the range [first,last], binary_op shall neither modify elements nor invalidate iterators or subranges.
さて実装ですが、タグディスパッチします。
template <class InputIterator, class T, class BinaryOperation> inline T foldr(InputIterator first, InputIterator last, T init, BinaryOperation binary_op) { return foldr_impl(first, last, init, binary_op, typename std::iterator_traits<InputIterator>::iterator_category()); }
まず、bidirectional iterator での実装は以下のようになります。
template <class BidirectionalIterator, class T, class BinaryOperation> inline T foldr_impl(BidirectionalIterator first, BidirectionalIterator last, T init, BinaryOperation binary_op, std::bidirectional_iterator_tag) { while (first != last) { --last; init = binary_op(*last, init); } return init; }
accumulate + reverse_iterator でも書けますが、decrement のコストが高い場合に遅くなる可能性があります。
次に forward iterator での実装です。一旦全ての iterator をコンテナに格納して、後からまとめて処理します。
template <class ForwardIterator, class T, class BinaryOperation> inline T foldr_impl(ForwardIterator first, ForwardIterator last, T init, BinaryOperation binary_op, std::forward_iterator_tag) { std::vector<ForwardIterator> v; for (; first != last; ++first) v.push_back(first); return std::accumulate(v.rbegin(), v.rend(), init, [&binary_op](T acc, ForwardIterator it) { return binary_op(*it, acc); }); }
再帰の方が直感的に書けますが、末尾再帰にもなりませんし、ライブラリコードにするのは気が引けます (しませんが)。
最後に input iterator での実装を考えます。上の forward iterator での実装は使えません。Input iterator の increment に関する要件の一部を 24.2.3 項から引用します。
++r
post: any copies of the previous value of r are no longer required either to be dereferenceable or to be in the domain of ==.
これによると、input iterator を increment したが最後、前の値のコピーは dereference できる保証がないものになってしまいます。それでは困るので、今回は iterator を進める段階で dereference し、その値をコンテナに格納していきます。
template <class InputIterator, class T, class BinaryOperation> inline T foldr_impl(InputIterator first, InputIterator last, T init, BinaryOperation binary_op, std::input_iterator_tag) { typedef typename std::decay<decltype(*first)>::type decayed_type; typedef decltype(*first) &&forwarded_type; std::vector<decayed_type> v; for (; first != last; ++first) v.push_back(*first); return std::accumulate(v.rbegin(), v.rend(), init, [&binary_op](T acc, typename std::conditional< std::is_same<decayed_type, bool>::value, bool, decayed_type & >::type value) { return binary_op(static_cast<forwarded_type>(value), acc); }); }
これでも、iterator の reference が copy/move 不可能な型への参照であった場合はどうしようもありません。Iterator の value_type を格納するようにしても、今度は reference に戻せる保証がありません。
色々考え出すと泥沼なので、この辺でやめておきます (投げた)。
追記: decayed_type が bool になる場合の対策をしました。