Type Class – RFoldable
The foldable introduces the functions which aggregate values. The lfold
, in particular, provides “forward” aggregation but the matching reverse aggregation is missing. This is because not every instance of foldable can be sensibly read in reverse, such as std::unordered_set
.
Right folds are important in computer science since they can be seen as a structural substitution of cons with an aggregation function and that concept remains important even though we don’t work with just linked lists. rfoldable
is an extension of foldable
which provides this additional functionality:
template<class T> struct rfoldable // : foldable { // Type value_type // B rfold(B(A,B),B,foldable<A>) static constexpr bool is_instance = false; }; // convenience functions template<class F, class B, class T> auto rfold(F&& f, B&& b, const T& in) { return rfoldable<T>::rfold(std::forward<F>(f),std::forward<B>(b),in); }
This demonstrates how type classes can be inherited much like the usual c++ class. Conceptually, it makes sense that something that can be folded from the right can also be folded from the left. Notice that the order of argument types in the function are switched: lfold
is of type B(B,A)
whereas rfold
is of type B(A,B)
.
Foldable had the fold
function which performed a left fold with seed and aggregation function provided by monoid
. This is not duplicated in rfoldable since the monoid operator is associative. An equivalent function using a right fold would give the exact same result.
The implementation is straightforward:
// std::shared_ptr template<class T> struct rfoldable<std::shared_ptr<T>> : public foldable<std::shared_ptr<T>> { // Type value_type using value_type = T; // B rfold(B(A,B),B,foldable<A>) template<class F, class B> static auto rfold(F&& f, B b, const T& in) -> B { if (in) b = ::fc::function::eval(f,b,*in); return b; } static constexpr bool is_instance = true; }; // containers template<class T> struct default_container_rfoldable : public default_container_foldable<T> { // Type value_type using value_type = typename ::fc::data::container_traits<T>::value_type; // B rfold(B(A,B),B,foldable<A>) template<class F, class B> static auto rfold(F&& f, B b, const T& in) -> B { for (auto a_it = in.begin(); a_it != in.end(); ++a_it) b = ::fc::function::eval(f,*a_it,b); return b; } static constexpr bool is_instance = true; };
It is interesting to note that rfold
and lfold
can be implemented in terms of each other. For example, rfold
can be written like this:
template<class T> struct rfoldable<T> : public foldable<T> { // ... // B rfold(B(A,B),B,foldable<A>) template<class F, class B> static auto rfold(F&& f, B b, const T& in) -> B { std::function<B(const B&)> identity = [](const B& b){return b;}; auto reverser = [&](std::function<B(const B&)>& g, const value_type& a) -> std::function<B(const B&)> { return [&,g](const B& b){return g(f(a,b));}; }; return lfold(reverser,identity,in)(b); } // ... };
Essentially, reverser transforms each element into a function which performs a single step of the aggregation. These functions are then composed using lfold
and the result is called with the seed.
Conceivably, one could create a variadic fold which aggregates over multiple foldables at once. The complexity there is that unlike map
, we now have a seed value and if we want some flexibility in the order of argument we now have to somehow specify which one is the seed.
Next time, we will introduce filtering, completing the trinity of map, filter and fold.
Edit: Didn’t even need generic lambdas!