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);
}
Venkat Shiva
  • 799
  • 1
  • 7
  • 9
  • 2
    Maybe you could give an example of your goal. For us don't-know-functional-idioms-very-well types that would help. – GManNickG Apr 02 '10 at 05: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. – Venkat Shiva Apr 02 '10 at 05: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. :) – GManNickG Apr 02 '10 at 05:24
  • 1
    I think an over-arching goal would still be very helpful for everyone. – GManNickG Apr 02 '10 at 05:37
  • @Venkat: Excellent thanks. Now that I get it...oh wait, already been answered. :) – GManNickG Apr 02 '10 at 05:54
  • Isn't this what the Boost library does? – Paul Johnson Apr 03 '10 at 10:13
  • [C++ templates are turing complete](http://stackoverflow.com/questions/189172/c-templates-turing-complete) – avandeursen Apr 06 '13 at 09:52

2 Answers2

86

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);
    }
};
rustyhu
  • 1,912
  • 19
  • 28
kennytm
  • 510,854
  • 105
  • 1,084
  • 1,005
  • 5
    So template parameters can be templates themselves? Great! I didn't know that! Thanks for the answer! :) – Venkat Shiva Apr 02 '10 at 05:51
  • 17
    I other words: the template system in C++ being (accidentally) Turing Complete it's quite incredible what you can do with it :) – Matthieu M. Apr 02 '10 at 08:41
  • 1
    what's the highest rank of higher order types that can be constructed with this tho? is `template – Erik Kaplun Mar 02 '14 at 03:44
  • 1
    @ErikAllik There's no natural limitation. You could do `template – kennytm Mar 03 '14 at 13:21
  • 7
    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`? – Electric Coffee Nov 05 '14 at 21:31
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 * -> *.

sth
  • 222,467
  • 53
  • 283
  • 367
  • 9
    The question is really about polymorphism over higher-kinded types, i.e. having *variables* with higher kinds. – Ganesh Sittampalam Apr 02 '10 at 10:25
  • 1
    @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. – sth Apr 02 '10 at 15:40