Higher-kinded Types with C++
-
23-09-2019 - |
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 areverse
function that works on any element type (theA
).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);
}
Solution
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);
}
};
OTHER TIPS
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 * -> *
.