Type Classes

Type classes are a feature of Haskell which is very similar to the upcoming Concepts. Both define interfaces to a data type, which can be defined separately from the data, in contrast to member functions.

To introduce the notion of type classes, let’s start with a simple one: the monoid. A monoid is an object which has a binary operation and an identity for that operation. For our purposes, we will call the identity empty() and the operation append.

The basic template for the type class follows:

template<class T>
struct monoid
{
    // T empty()
    // T append(T,T)
    static constexpr bool is_instance = false;
};

Most things are not monoids and so we also add a boolean which marks this. This allows us to do type checking using std::enable_if or static_assert.

When an object has the type class interface, we say that it is an instance of the type class. For example, the monoid instance for integers can be written as:

template<>
struct monoid<int>
{
    static int empty(){return 0;}
    static int append(int lhs, int rhs){return lhs+rhs;}
    static constexpr bool is_instance = true;
};

Now if we wanted to write a function using monoids, we could do so easily and with guarantees of type safety. For example, here is a function which “accumulates” monoid values from a vector:

template< 
    class T,
    class = typename std::enable_if<monoid<T>::is_instance>::type
    >
T accumulator(const std::vector<T>& in)
{
    T out{monoid<T>::empty()};

    for (const T& t : in)
        out = monoid<T>::append(out,t);

    return out;
}

int main()
{
    std::cout << accumulator(std::vector<int>{1,2,3}) << "\n";

    return 0;
}

Output:

6

Obviously, there are quite a few data types which display monoid behaviour, including all the fundamental data types. There’s quite a bit of repetition which can be removed, also reducing the chance for error.

Many of the monoids, including all the fundamental types implement operator+ and are value-initialized to a reasonable value. A default monoid can be written to represent this.

template<class T>
struct default_monoid
{
    static T empty(){return T{};}
    static T append(const T& lhs, const T& rhs){return lhs+rhs;}
    static constexpr bool is_instance = true;
};

// example use
template<>
struct monoid<int> : public default_monoid<int>
{};

template<>
struct monoid<char> : public default_monoid<char>
{};

We can further reduce the repetition through the use of x macros:

#define FUNDAMENTAL_TYPES\
    X(bool)\
    X(signed char)\
    X(unsigned char)\
    X(char)\
    X(wchar_t)\
    X(char16_t)\
    X(char32_t)\
    X(short)\
    X(unsigned short)\
    X(int)\
    X(unsigned)\
    X(long)\
    X(unsigned long)\
    X(long long)\
    X(unsigned long long)

#define X(a)\
    template<>\
    struct monoid<a> : public default_monoid<a>\
    {};

FUNDAMENTAL_TYPES;
#undef X

This code will generate monoid instances based on default_monoid for all the fundamental data types.

We can also use default_monoid for strings:

template<>
struct monoid<std::string> : public default_monoid<std::string>
{};

But for some types we need to customize a bit more:

template<class T>
struct monoid<std::vector<T>>
{
    static std::vector<T> empty(){return std::vector<T>{};}

    static std::vector<T> append(std::vector<T> lhs, const std::vector<T>& rhs)
    {
        for (const T& t : rhs)
            lhs.push_back(t);

        return lhs;
    }

    static constexpr bool is_instance = true;
};

I’m not going to go into every single type but, suffice it to say that containers, string streams, numerical types and many more can all instantiate the monoid type class.

The combination of generic programming and functional programming is very powerful. The accumulator function from earlier can now work with every type that is an instance of monoid! Pretty neat.

int main()
{
    int a = accumulator(std::vector<int>{1,2,3});
    std::cout << a << "\n";

    int b = accumulator(accumulator(std::vector<std::vector<int>>{{1,2,3},{4,5,6},{7,8,9}}));
    std::cout << b << "\n";

    std::string c = accumulator(std::vector<std::string>{"hello ","world","!"});
    std::cout << c << "\n";

    return 0;
}

Output:

6
45
hello world!
About these ads

5 comments

  1. Andrzej Krzemieński

    Hi, one thing that struck me when reading the post is that a type can model a concept like Monoid in more than one way. For instance, int with operator+ and neutral element 0 does model Monoid, but also the same type int with operator* and neutral element 1 models Monoid.

    To me it looks like it is not the type that models Monoid but a pair: a type and a binary operation. This could be reflected in the ‘concept’ as two template parameters:

    template <typename Type, typename BinaryOp = std::plus<Type>>
    struct Monoid
    {
      // ...
    };
    
    • whanhee

      Thanks for the suggestion! Later on, I will be dealing with some more uses for monoids so I use this as sort of a “default” implementation to simplify things. Certainly having 2 parameters is more mathematically correct though.

  2. Pingback: Second Lesson | programmercenter
  3. karsten

    And you also need the identity element. For std::multiplies you have to provide 1 as the identity.

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