Tagged: functor

Zipper and other Function Objects

There are some useful function objects, which can be used with mappable.

Zippers and pairers pack things into tuples and pairs respectively:

struct zipper
{
    template<class... Args>
    auto operator()(Args&&... args)
    {
        return std::make_tuple(std::forward<Args>(args)...);
    }
};

struct pairer
{
    template<class L,class R>
    auto operator()(L&& l, R&& r)
    {
        return std::make_pair(std::forward<L>(l),std::forward<R>(r));
    }
};

If you need to pack constant values or references, you can use a variation on this concept. The pair variant is particularly useful for inserting values into std::map.

template<class... Args>
struct zipper_t
{
    template<class... Args_>
    auto operator()(Args_&&... args)
    {
        return std::tuple<Args...>(std::forward<Args_>(args)...);
    }
};

template<class L,class R>
struct pairer_t
{
    template<class L_,class R_>
    auto operator()(L_&& l, R_&& r)
    {
        return std::pair<L,R>(std::forward<L_>(l),std::forward<R_>(r));
    }
};

Following the nomenclature of std::make_pair and std::make_shared, make just makes an object. This is quite useful since you can’t get a pointer to a constructor.

template<class T>
struct make
{
    template<class... Args>
    auto operator()(Args&&... args)
    {
        return T(std::forward<Args...>(args...));
    }
};

Less type strict versions of std::plus and its siblings are useful for when you need to operate on different types, such as matrices and vertices.

#define FC_BINARY_OPERATORS\
    X(plus,+)\
    X(minus,-)\
    X(multiplies,*)\
    X(divides,/)\
    X(modulus,%)\
    X(equal_to,==)\
    X(not_equal_to,!=)\
    X(greater,>)\
    X(less,<)\
    X(greater_equal,>=)\
    X(less_equal,<=)\
    X(logical_and,&&)\
    X(logical_or,||)\
    X(bit_and,&)\
    X(bit_or,|)\
    X(bit_xor,^)

#define X(name,symbol)\
    struct name\
    {\
        template<class L,class R>\
        auto operator()(L&& l, R&& r)\
        {\
            return l symbol r;\
        }\
    };

FC_BINARY_OPERATORS
#undef X

There also exist functions unzip and unpair which are also members of mappable analogous to the Haskell unzip. For example, unpairing a vector of tuples gives a pair of vectors:

template<class L,class R>
auto unpair(std::vector<std::pair<L,R>>&& v)
{
    std::pair<std::vector<L>,std::vector<R>> out;

    for (auto& p : v)
    {
        out.first.push_back(p.first);
        out.second.push_back(p.second);
    }

    return out;
}

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.