61

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); }
Improve this question
7
  • 2
    Maybe you could give an example of your goal. For us don't-know-functional-idioms-very-well types that would help. Commented Apr 2, 2010 at 5:17
  • 1
    @GMan: I could give an example, but I'm well aware it will hardly mean anything except for the people who know it already. So I didn't bother to include an example. Commented Apr 2, 2010 at 5:21
  • 1
    @Venkat: I mean a goal, what's your bigger picture? You want a higher-kinded type for: __________. Also, a very simple example with comments would still be better than nothing. :) Commented Apr 2, 2010 at 5:24
  • 1
    I think an over-arching goal would still be very helpful for everyone. Commented Apr 2, 2010 at 5:37
  • @Venkat: Excellent thanks. Now that I get it...oh wait, already been answered. :) Commented Apr 2, 2010 at 5:54

2 Answers 2

Reset to default
88

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 Maybe<b>{true, b{}}; else return function(action.value); } };
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

So template parameters can be templates themselves? Great! I didn't know that! Thanks for the answer! :)
I other words: the template system in C++ being (accidentally) Turing Complete it's quite incredible what you can do with it :)
what's the highest rank of higher order types that can be constructed with this tho? is template <template <template ...> > > allowed?
@ErikAllik There's no natural limitation. You could do template <template <template <template <...> class> class> class m>.
what I'm more interested in, is how this higher-kinded struct is used... Could I get you to add an example that uses mbind in conjunction with Maybe and Monad<Maybe>?
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 * -> *.

Improve this answer

2 Comments

The question is really about polymorphism over higher-kinded types, i.e. having variables with higher kinds.
@Ganesh: Yeah, by now it is. In the beginning it just asked if there were types of higher kinds, so I didn't mention templates as template parameters to not complicate things necessarily.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.