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 になる場合の対策をしました。