Variadic Mapping

Last time we discussed the Mappable type class which is similar to the Functor type class of Haskell.

When dealing with lists, Haskell also provides the zipWith function which allows you to “map” over 2 lists at once. For example, this

zipWith (+) [1,2,3] [4,5,6,7]

results in

[5,7,9]

zipWith matches each element in the same position and applies a function, in this case addition, and then constructs a new list with the results. If there is no match, extra elements are ignored. If you want to do more lists at once, there is also zipWith3, zipWith4, all the way to zipWith7.

With variadic functions and templates, the map function can be extended to generalize both map and variations of zipWith! The new mappable type class can be written as:

template<class T>
struct mappable
{
    // Type value_type
    // mappable<R> map(R(A,Args...),mappable<A>,mappable<Args>...)
    static constexpr bool is_instance = false;
};

map is now a variadic function which takes a function and at least one mappable.

Some template machinery is needed to provide underlying functionality. This will vary for different mappables, so for this post we will focus on containers.

We will want to iterate over every container at the same time, terminating whenever we reach any of the ends. This can be done using a tuple of iterators and some helper functions:

// Helper class
template<size_t index>
struct tuple_helper
{
    template<class... Args>
    static bool any_equal(const std::tuple<Args...>& lhs, const std::tuple<Args...>& rhs)
    {
        if (std::get<index>(lhs) == std::get<index>(rhs))
            return true;

        return tuple_helper<index-1>::any_equal(lhs,rhs);
    }

    template<class... Args>
    static void increment(std::tuple<Args...>& a)
    {
        tuple_helper<index-1>::increment(a);
        std::get<index>(a)++;
    }

    template<class Tuple,class... Args>
    static auto dereference(Tuple&& t, Args&&... args)
    {
        return tuple_helper<index-1>::dereference(
            std::forward<Tuple>(t),
            std::get<index>(std::forward<Tuple>(t)),
            std::forward<Args>(args)...
            );
    }
}

// Terminate template recursion
template<>
struct tuple_helper<0>
{
    template<class... Args>
    static bool any_equal(const std::tuple<Args...>& lhs, const std::tuple<Args...>& rhs)
    {
        return std::get<0>(lhs) == std::get<0>(rhs);
    }

    template<class... Args>
    static void increment(std::tuple<Args...>& a)
    {
        std::get<0>(a)++;
    }

    template<class Tuple,class... Args>
    static auto dereference(Tuple&& t, Args&&... args)
    {
        return std::tuple<decltype(*std::get<0>(t)),decltype(*args)...>(
            *std::get<0>(t),(*args)...);
    }
}

// Check if any tuple elements are equal
template<class A,class... Args>
bool tuple_any_equal(const std::tuple<A,Args...>& lhs, const std::tuple<A,Args...>& rhs)
{
    return tuple_helper<sizeof...(Args)>::any_equal(lhs,rhs);
}

// Increment all tuple elements
template<class A,class... Args>
void tuple_increment(std::tuple<A,Args...>& a)
{
    tuple_helper<sizeof...(Args)>::increment(a);
}

// Dereference iterators
template<class Tuple>
auto tuple_dereference(Tuple&& t)
{
    return tuple_helper<std::tuple_size<typename std::remove_reference<Tuple>::type>::value-1>
        ::dereference(std::forward<Tuple>(t));
}

These functions essentially allow us to write a for loop over multiple containers at the same time by packing iterators into a tuple.

In combination with tuple forwarding, we can write some pretty neat code. To replicate the Haskell example above:

int main()
{
    std::vector<int> a{1,2,3};
    std::vector<int> b{4,5,6,7};

    const auto ends = std::make_tuple(a.end(),b.end());
    for (auto iters = std::make_tuple(a.begin(),b.begin());
         !tuple_any_equal(iters,ends);
         tuple_increment(iters))
    {
        std::cout << tuple_eval(std::plus<int>(),tuple_dereference(iters)) << " ";
    }

    return 0;
}

Which outputs:

5 7 9

Of course, we want to hide all of that iterator business away inside of the map function. Thus we can rewrite the container mappable instance like this:

template<class T>
struct default_container_mappable
{
    // Type value_type
    using value_type = typename container_traits<T>::value_type;

    // mappable<R> map(R(A,Args...),mappable<A>,mappable<Args>...)
    template<class F,class A,class... Args>
    static auto map(F&& f, const A& in, const Args&... args)
        -> typename container_traits<T>::template rebind<
            decltype(eval(f,
                std::declval<typename container_traits<A>::value_type>(),
                std::declval<typename container_traits<Args>::value_type>()...
                ))>
    {
        using B = decltype(eval(f,
            std::declval<typename container_traits<A>::value_type>(),
            std::declval<typename container_traits<Args>::value_type>()...
            ));
        using T_B = typename container_traits<T>::template rebind<B>;

        T_B out;

        const auto ends = std::make_tuple(in.end(),(args.end())...);

        for (auto iters = std::make_tuple(in.begin(),(args.begin())...);
             !tuple_any_equal(iters,ends);
             tuple_increment(iters))
        {
            container_traits<T_B>::add_element(out,
                tuple_eval(std::forward<F>(f),tuple_dereference(iters)));
        }

        return out;
    }

    static constexpr bool is_instance = true;
};

// variadic convenience function
template<class F, class T, class... Args>
auto map(F&& f, const T& in, const Args&... args)
{
    return mappable<T>::map(std::forward<F>(f),in,args...);
}

And we can simply write:

int main()
{
    std::vector<int> a{1,2,3};
    std::vector<int> b{4,5,6,7};

    for (int n : map(std::plus<int>(),a,b))
        std::cout << n << " ";

    return 0;
}

You can do this for any instance of mappable, though it’s sometimes tricky. For instance, the function instance makes use of multi_tuple_eval to evaluate multiple functions with multiple parameters.

The full code and examples for std::shared_ptr and functions are available here.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s