Higher-kinded Types with C++

Question

This question is for the people who know both Haskell (or any other functional language that supports Higher-kinded Types) and C++...

Is it possible to model higher kinded types using C++ templates? If yes, then how?

EDIT :

From this presentation by Tony Morris:

Higher-order Polymorphism :

• Languages such as Java and C# have first-order polymorphism because they allow us to abstract on types. e.g. List<A> can have a reverse function that works on any element type (the A).

• More practical programming languages and type systems allow us to abstract on type constructors as well.

• This feature is called higher-order (or higher-kinded) polymorphism.

Example :

Pseudo-Java with an invented notation for higher-order polymorphism

interface Transformer<X, Y> {
  Y transform(X x);
}

interface Monad<M> { // M :: * -> *
  <A> M<A> pure(A a);
  <A, B> M<B> bind(Transformer<A, M<B>> t, M<A> a);
}

Answer 1

Functors are an example of a higher order type, and often templates are used to work with them in C++.

Maybe these links would interest you?

http://en.wikipedia.org/wiki/Function_object

http://en.wikipedia.org/wiki/Map_(higher-order_function)

http://en.wikipedia.org/wiki/Fold_(higher-order_function)

Answer 2

c++0x has support for lambda expressions, which can also be stored in function types. For example:

std::tr1::function<void (int)> g = [](int n) { std::cout << n << " "; };

produces a function object g that prints an integer to cout. You can then call g as you would any other function:

g(123);

or pass it to other functions such as:

std::vector<int> v = ...
std::for_each(v.begin, v.end, g);

to print out the contents of the vector v.

Answer 3

Isn't usually a normal template already a higher-kinded type? For example std::vector takes a type parameter to create an actual type like std::vector<int>, so it has kind * -> *.

Answer 4

Template-template parameters?

template <template <typename> class m>
struct Monad {
    template <typename a>
    static m<a> mreturn(const a&);

    template <typename a, typename b>
    static m<b> mbind(const m<a>&, m<b>(*)(const a&));
};

template <typename a>
struct Maybe {
    bool isNothing;
    a value;
};

template <>
struct Monad<Maybe> {
    template <typename a>
    static Maybe<a> mreturn(const a& v) {
        Maybe<a> x;
        x.isNothing = false;
        x.value = v;
        return x;
    }

    template <typename a, typename b>
    static Maybe<b> mbind(const Maybe<a>& action, Maybe<b>(*function)(const a&)) {
        if (action.isNothing)
            return action;
        else
            return function(action.value);
    }
};