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!

Leave a comment