C ++ Type Classes

It has already been described how to implement monads in C ++ without type classes . I want to show how you can implement type classes using the monad as an example.
This technique is widely used in the Scala language, but can also be used in C ++. I briefly described it as an illustration of the difficulties of a unified library description , but now I will demonstrate its implementation.
It should be noted that type classes are used not only in declarative languages ​​like Haskell and Mercurry, but they are reflected in rather classical Go and Rust.
This technique is also suitable for implementing multi methods from Common Lisp and Clojure.

I haven't taken C ++ in my hands for six years, so the code may not be ideal and not use new (useful) features.
In addition, I completely ignore the problem of memory management - C ++ practitioners will do it better than me.
The efficiency of the code was checked on gcc 4.7.3.


The main idea of ​​type classes is to separate the interface implementation from the data structure. The same interface can be used to work with completely different data structures, and for each data type must be implemented separately. Code using this interface is not required to know the details of its implementation.
With complexity monads, it adds that this interface is implemented for a generic type that is parameterized by another type.
')
The interface implementation must be stored somewhere, and we only have classes for this:

#include <stddef.h> template <template<typename _> class M> class monadVTBL { public: template<typename v, typename x> static M<v> bind(M<x>, M<v>(*)(x)); template<typename v> static M<v> mreturn(v); }; template<template<typename _> class M, typename v, typename x> M<v> bind(M<x> i, M<v>(*f)(x), monadVTBL<M> *tbl = NULL) { return monadVTBL<M>::bind(i, f); } template<template<typename _> class M, typename v> M<v> mreturn(vi, monadVTBL<M> *tbl = NULL) { return monadVTBL<M>::mreturn(i); } 

As we see, the implementation is passed to the functions using it as an additional parameter with the default value. In this case, we need only the type of this parameter (for this reason it is always NULL), and we could transfer it to a local variable. The use of the parameter provides additional flexibility, which, with some effort, will save memory on instantiating templates (functions will have to be hidden in classes that inherit the implementation of generalized functions through void *) and will be useful for implementing multi-methods.

 template <template<typename _> class M> M<char> inc(char c) { return mreturn<M,char>(c+1); } 

A fairly simple function using the monad.
On Haskell, she will crawl

 inc :: (Monad m) => Char -> m Char inc c = return (succ c) 

return here means completely different than in C ++.

We now turn to the implementation of the monad IO. The objects that the monad interface works with in this case are I / O operations. In Haskell, these are normal values; in C ++, they will be modeled by classes.

 #include<stdio.h> template<typename v> class IOop { public: virtual v run() = 0; }; template<typename v> class IOm { public: IOop<v> *op; IOm(IOop<v> *o) { op = o; } v run() { op->run(); } }; 

The run method performs this operation (in Haskell, in fact, it is called by the runtime system on the main object).
The IOm container class is needed to hide the type of operation, which can be of variable size.
As we see, these classes do not connect anything other than the name with monads, and they don’t know anything about monads. This is an important advantage of type classes over ordinary classes that need to know their interface.

 class getChar: public IOop<char> { public: getChar() {} virtual char run() { return getchar(); } } _getChar[1]; IOm<char> getChar(_getChar); typedef class unit { } unit; unit Unit; class _putChar: public IOop<unit> { char v; public: _putChar(char c) { v = c; } virtual unit run() { putchar(v); return Unit; } }; class IOm<unit> putChar(char c) { IOm<unit> o(new _putChar(c)); return o; }; 

And here are two specific I / O operations — get the character from the standard input and output the character to the standard output. As well as a function that turns a character into an operation that outputs it.

 template<typename v> class mconst: public IOop<v> { vr; public: mconst(vx) { r=x; } virtual v run() { return r; } }; 

This class implements the monadic “return” operation, which in this case creates an I / O operation, which always “inputs” a constant.

 template<typename v, typename i> class mbind: public IOop<v> { IOop<i> *s; IOm<v> (*f)(i); public: v run() { return (*f)(s->run()).run(); } mbind(IOop<i> *x, IOm<v> (*g)(i)) { s=x; f=g; } }; 

And this operation ">> =", which links the monad with the generator of the new monad.

 template<> class monadVTBL<IOm> { public: template<typename v, typename i> static IOm<v> bind(IOm<i> x, IOm<v>(*f)(i)) { IOm<v> b(new mbind<v,i>(x.op,f)); return b; } template<typename v> static IOm<v> mreturn(vx) { IOm<v> r(new mconst<v>(x)); return r; } }; 

And here is the most important thing - specialization of the monad implementation for IO.

 template<typename i> IOm<unit> ignNL(iv) { return bind<IOm,unit,char>(mreturn<IOm,char>('\n'),putChar); } 

This is an IO generator that ignores the result of the previous monad and prints '\ n'.

 ign :: a -> IO () ign _ = putChar '\n' 

For IO (and some other monads, for example parsers), ignoring the previous monad is quite a popular operation and for it there is a function:

 (>>) :: (Monad m) => ma -> mb -> mb a >> b = a >>= \_ -> b 

And now let's check how it all works:

 bind<IOm,unit,unit>(bind<IOm,unit,char>(bind<IOm,char,char>(getChar,inc),putChar),ignNL<unit>).run(); 

We read a character from standard input, increment it, print it, and print a newline.

And now we are implementing the monad interface for another class that knows even less about monads.

 #include<vector> template<typename v> class myvector: public std::vector<v> { }; 

Unfortunately, the std :: vector template has two parameters (the second is responsible for the allocation policy and can be substituted by default). Modern gcc does not allow it to be transferred to a template that waits for a template with one parameter (if memory serves me, before there were no such strictness). So you have to create a simple wrapper.

 template<> class monadVTBL<myvector> { public: template<typename v, typename i> static myvector<v> bind(myvector<i> x, myvector<v>(*f)(i)){ myvector<v> e; for(typename myvector<i>::iterator it = x.begin(); it != x.end(); ++it) { myvector<v> c = f(*it); for(typename myvector<v>::iterator i = c.begin(); i != c.end(); ++i) { e.push_back(*i); } } return e; } template<typename v> static myvector<v> mreturn(vx) { myvector<v> e; e.push_back(x); return e; } }; 

The functionality of the monad std :: vector is similar to the functionality of the monad List in Haskell.

We try how it works:

  myvector<char> x; x.push_back('q'); x.push_back('w'); x.push_back('e'); myvector<char> z = bind<myvector,char,char>(x,inc); for(typename myvector<char>::iterator i = z.begin(); i != z.end(); ++i) { std::cout << *i; } 

For such functionality, the “functor” type class would be enough, but I did not want to invent a more complex example.