Haskell typeclasses and C++ template classes

Question

Is it possible to emulate the type class functionality of Haskell with C++ (or C#) templates?

Does it make sense or is there any payoff in doing that?

I was trying to make a Functor class in C++ and I wasn't able. I tried something like this:

#include <iostream> using namespace std;  //A function class to make types more readable template <class input, class output> class Function { private:   output (*ptrfunc )(input); public:   Function(output (* ptr)(input)) {     ptrfunc = ptr;   }   output call(input x) {return  (*ptrfunc)(x);}   output operator() (input x) { return call(x);} };   //the functor "typeclass" template <class a> class Functor{ public:   template <class b> Functor<b> fmap(Function<a,b> func); };  // an container type to be declared "instance" of functor: template <class a> class List : public Functor<a> {  private:   a * ptrList;   int size; public:   List(int n) {  //constructor;     ptrList = new a[n];      size = n;   }   List(List<a> const& other) { //copy constructor     size = other.size;     ptrList = new a[size];     for(int i = 0; i<size; i++)       (*this)[i] = other[i];   }   ~List() { delete ptrList;} //destructor   a& operator[](int i) { return ptrList[i];} // subscript operator just for easy notation   const a& operator[](int i) const { return ptrList[i];}// subscript operator just for easy notation    template <class b> List<b> fmap(Function<a,b> func) { //"instance" version of fmap     List<b> temp(size);     for(int i = 0; i < size; i++)       temp[i] = func((*this)[i]);     return temp;   } };   int test(int k) { return 2 * k;}  int main(void) {   Function<int, int> func(&test);   List<int> lista(10);   for(int i = 0; i < 10; i++)     lista[i] = i;   List<int> lista2(lista.fmap(func));   for(int i = 0; i < 10; i++)     cout << lista2[i] << " ";   cout << endl;   return 0; } 

It does what it's supposed to do, but does it make any sense to use this pattern in C++? Is it really the same pattern as in haskell:

data List a = -- some stuff   class  Functor f  where fmap :: (a -> b) -> f a -> f b  instance (Functor List) where -- some stuff     

It doesn't seem to be the same thing to me, cause in Functor f, f is a kind * -> * type constructor, and in my definition above in Functor<a>, a is not a template a<something>, but the "contained" data type itself.

Is there a way out to this? And more importantly: it makes sense to try to copy this kinds of patterns to C++? It seems to me that C# is more akin to functional programming style than C++. Is there a way to do this in C#?

Answer 1

Is it possible to emulate the type class functionality of Haskell with C++ (or C#) templates?

I am not sufficiently versed in C++ templates to answer the question. I can talk about C# generic types a bit though.

The short answer is, no. The Haskell system of "higher" type classes is more powerful than the generic type system in C#.

A brief discussion of what we mean by "higher types" might be useful at this point for any readers that are still reading this who are not familiar with Haskell. In C# you can do this:

interface IEnumerable<T> { ... } 

The "generic" type "IEnumerable of one type parameter" is not really a "type" per se, it is a pattern from which you can construct infinitely many new types, by substituting type arguments ("int") for type parameters ("T"). In that sense it is "higher" than a normal type.

You can put constraints on type parameters of generic types:

class C<T> where T : IEnumerable<int> 

Generic type C can be constructed with any type argument, so long as the type argument is a type that is implicitly convertible via reference or boxing conversion to IEnumerable<int>.

But the Haskell type system goes one step further than that. It supports "type classes" where the constraints you can put on the T are things like "T has an equality operator defined on it". In C#, operators are defined as static methods, and there is no analogue of an interface for static methods. We have no way in C# of generalizing across many types based on arbitrary static methods.

An example usually given for Haskell is the "monad" pattern. In C# notation, suppose we have a type:

class MyMonad<T> {     public static MyMonad<TOut> Bind<TIn, TOut>(MyMonad<TIn>, Func<TIn, MyMonad<TOut>>) { ... }     public MyMonad(T t) { ... } } 

A monad is just a pattern; a monadic type is any generic type such that it has a static generic method Bind and a constructor that matches the pattern above. In Haskell you can use higher types to describe that pattern; in C#, we have no facility in the type system for generalizing on things like static methods and constructors.

Or, you might say that it would be more idiomatic to use an instance binder:

class MyMonad<T> {     public MyMonad<TOut> Bind<TOut>(MyMonad<T>, Func<T, MyMonad<TOut>>) { ... }     public MyMonad(T t) { ... } } 

Does that help? No. Even leaving the problem with the constructor aside, we cannot come up with an interface that captures this pattern. We can try:

interface IMonad<T> {     public IMonad<TOut> Bind<TOut>(IMonad<T>, Func<T, IMonad<TOut>>); } 

But that is not right. That says that a monad is something that takes a monad and a function that returns a monad in, and returns a monad. That means that you could have two implementations of IMonad<T>, say Maybe<T> and Sequence<T> and then have a binder that takes a sequence and returns a maybe! That doesn't make any sense; the pattern we want to capture is

highertype Monad makes a pattern with TheImplementingType<T> like {     public TheImplementingType<TOut> Bind<TOut>(TheImplementingType<T>, Func<T, TheImplementingType<TOut>>); } 

but we have no way of expressing that in C#.

Let's consider your Functor example. In C# we might have a type

class List<T>  {     public static List<TOut> Map<TIn, TOut>(Func<TIn, TOut> mapper, List<TIn> list)      { ... } 

Or, perhaps more idiomatically, an instance method:

class List<T>  {     public List<TOut> Map<TOut>(Func<T, TOut> mapper)      { ... } 

Or, again more idiomatically, we might have the static method as an extension method. (In fact, this method does exist in the sequence operator library in C#; it can be built by composing "Select" on IEnumerable<T> with "ToList").

Whatever. Doesn't matter. The point is that in your code in Haskell:

class  Functor f  where  fmap :: (a -> b) -> f a -> f b  

You can say that "any generic type which exposes a mapping operation that meets the pattern above is said to be a 'Functor'", and then you can make methods that take Functors. We don't have any way of generalizing "all the types that provide mapping operations" at the user level in C#.

To get around this limitation of the type system, what we've done is chosen a few of the most powerful higher types and built them directly into the language. The language itself recognizes higher types like the sequence pattern (in the foreach loop processing), the generalized monad pattern (in query comprehensions; "SelectMany" is "Bind" on an arbitrary monad), the continuation pattern (in "await" coming in C# 5), the "Maybe" monad (in nullable value types) and so on.

So to solve your specific problem, yes, no problem, the notion of making a projection is not captured in the type system but it is captured in the language with LINQ query comprehensions. If you say

from x in y select z 

then any expression y of a type that has a Select method that takes y and a mapping from x to z will work. That pattern has been built into the C# language. But if you want to describe some other "higher" pattern, you're out of luck.

It would be nice to have a facility in the type system to describe higher types, but what is more likely is that we will keep the type system as-is, and bake more patterns into the language as-needed.

A place where I commonly see an attempt to emulate higher-order types in C# is described in this question:

Why does this generic constraint compile when it seems to have a circular reference

The idea here is that the developer wishes to develop a type "Animal" such that:

abstract class Animal {     public abstract void MakeFriends<T>(T newFriend)     where T : THISTYPE; } 

The fictional "where T : THISTYPE" is attempting to get across the idea that a Cat can only make friends with another Cat, a Dog can only make friends with another Dog, and so on. (Ignore for the moment the fact that such a pattern, which implies that MakeFriends has virtual covariance on formal parameter types, would not be typesafe and would probably thereby violate the Liskov Substitution Principle.) That concept is expressible in higher types, but not in the C# type system. People sometimes use a pattern like:

abstract class Animal<T> where T : Animal<T> {     public abstract void MakeFriends(T newFriend); } class Cat : Animal<Cat> {     public override void MakeFriends(Cat newFriend){ ... } } 

However, this fails to actually enforce the desired constraint, because of course there is nothing whatsoever stopping you from saying:

class Dog : Animal<Cat> {     public override void MakeFriends(Cat newFriend){ ... } } 

And now a Dog can be friends with a Cat, violating the intention of the author of Animal. The C# type system is simply not powerful enough to represent all the sorts of constraints that you might want. You'd have to use higher types to make this work properly.

Answer 2

C++0x was going to introduce concepts which are quite similar to Haskell's type classes, but the feature got voted out. Be patient for another ten years, and they may finally make their way into the language.