Type Class – Mappable

Previously, we have introduced the concept of type classes with the monoid. The next type class to look at is the mappable type class, representing “things” that can be mapped. This class is quite similar to the Functor type class in Haskell.

An instance of mappable is something that can be queried for values, such as std::vector, std::shared_ptr or std::function. The function map basically lets you transform the values of a query. It is essentially a generalized functional style std::transform.

Mapping becomes an even more powerful as our repertoire of type classes expands, especially with folding and filtering, but let’s not get ahead of ourselves.

The mappable type class:

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

The type class lets you determine the result of a query to a mappable using value_type. It also contains the map function, which is specialized by each instance.

Mapping a function (or function-like object) will return a new function with its return value modified:

template<class Result,class... Params>
struct mappable<Result(Params...)>
{
    // Type value_type
    using value_type = Result;

    // mappable<R> map(R(A),mappable<A>)
    template<class F,class A>
    static auto map(F&& f, const A& in)
    {
        return [=](Params... params)
        {
            return eval(f,eval(in,std::forward<Params>(params)...));
        };
    }

    static constexpr bool is_instance = true;
};

// const member function
template<class Result, class Class, class... Params>
struct mappable<Result(Class::*)(Params...) const> :
    public mappable<Result(const Class&,Params...)>
{};

// member function
template<class Result, class Class, class... Params>
struct mappable<Result(Class::*)(Params...)> :
    public mappable<Result(Class&,Params...)>
{};

// member object
template<class Result, class Class>
struct mappable<Result(Class::*)> :
    public mappable<Result(const Class&)>
{};

// free function
template<class Result, class... Params>
struct mappable<Result(*)(Params...)> :
    public mappable<Result(Params...)>
{};

Notice that the Result type doesn’t matter for the purposes of map, only the parameters (Params...) do. For example:

template<int X>
int increment_by(int n){return n+X;}

// still returns an integer
auto func = mappable<char(const std::string&)>::map(&increment_by<1>,&std::string::size);

We have to specify const std::string& because we can’t turn Params... into universal references, though that would be a nice improvement.

Generally, it’s the “shape” of the mappable that determines what can be mapped. For functions, the parameters types determine the shape. For pointers, it might be the particular type of pointer. For containers, it would be the type of container used.

To reflect this, we will make use of container_traits to write the container instances:

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

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

        T_B out;

        for (auto& a : in)
            container_traits<T_B>::add_element(out,eval(std::forward<F>(f),a));

        return out;
    }

    static constexpr bool is_instance = true;
};

#define FC_DEFAULT_CONTAINER_MAPPABLE(T)\
    template<class... Args>\
    struct mappable<T<Args...>> : public default_container_mappable<T<Args...>>\
    {};

FC_DEFAULT_CONTAINER_MAPPABLE(std::deque);
FC_DEFAULT_CONTAINER_MAPPABLE(std::list);
FC_DEFAULT_CONTAINER_MAPPABLE(std::multiset);
FC_DEFAULT_CONTAINER_MAPPABLE(std::set);
FC_DEFAULT_CONTAINER_MAPPABLE(std::basic_string);
FC_DEFAULT_CONTAINER_MAPPABLE(std::unordered_multiset);
FC_DEFAULT_CONTAINER_MAPPABLE(std::unordered_set);
FC_DEFAULT_CONTAINER_MAPPABLE(std::vector);

As with functions, the type of container passed in doesn’t matter. The actual type returned by map has the same “shape” as specified in the specific instance of mappable, but rebound to a new value_type.

If you want to just keep the same “shape”, a convenience function can be used which automatically determines the output:

template<class F, class T>
auto map(F&& f, const T& in)
{
    return mappable<T>::map(std::forward<F>(f),in);
}

To demonstrate how mappable can be used:

int main()
{
    // function
    std::string words = "hello, world!";
    auto string_length_plus_one = 
        mappable<char(const std::string&)>::map(&increment_by<1>,&std::string::size);
    std::cout << "size + 1:         " << string_length_plus_one(words) << "\n";

    // container with convenience function
    auto shout = [](char c){return std::toupper(c,std::locale::classic());};
    std::cout << "shout:            " << map(shout,words) << "\n";

    // container to different container
    std::cout << "characters used:  ";
    for (char c : mappable<std::set<char>>::map([](char a){return a;},words))
        std::cout << "(" << c << ") ";
    std::cout << "\n";

    return 0;
}

Which gives the output:

size + 1:         14
shout:            HELLO, WORLD!
characters used:  ( ) (!) (,) (d) (e) (h) (l) (o) (w)

Working code available here, with a few more examples too!

Note: It goes without saying that you shouldn’t combine this with using namespace std because of std::map.

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