Уже было описано как реализовать монады на C++ без классов типов. Я же хочу показать, как можно реализовать классы типов, использую в качестве примера монады.
Этот прием широко применяется в языке Scala, но может быть использован и в C++. Кратко я его описал в качестве иллюстрации трудностей унифицированного описания библиотек, сейчас же продемонстрирую его реализацию.
Нужно отметить что классы типов применяются не только в декларативных языках, как Haskell и Mercurry, но о нашли свое отражение в достаточно классических Go и Rust.
Этот прием так же подходит для реализации мультиметодов из Common Lisp и Clojure.
C++ я не брал в руки уже лет шесть, так что код может быть не идеоматичным и не использовать новые (полезные) фичи.
Кроме того, я полностью игнорирую проблему управления памятью — практикующие C++ справятся с этим лучше меня.
Работоспособность кода проверялась на gcc 4.7.3.
Основная идея классов типов в отделении реализации интерфейса от структуры данных. Один и тот же интерфейс может использоваться для работы с совершенно разными структурами данных, и для каждого типа данных должен реализовываться отдельно. Код, использующий этот интерфейс, не обязан знать подробности его реализации.
С монадами сложности добавляет то, что этот интерфейс реализуется для обобщенного типа, параметризованного другим типом.
Реализация интерфейса должна где-то храниться, а у нас для этого есть только классы:
#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(v i, monadVTBL<M> *tbl = NULL) {
return monadVTBL<M>::mreturn(i);
}
Как мы видем, реализация передается в использующие ее функции в качестве дополнительного параметра со значением поумолчанию. В данном случае нам достаточно только типа этого параметра (по этому он всегда NULL), и мы могли бы перенести его в локальную переменную. Использование параметра дает дополнительную гибкость, которая при некотором старании позволит сэкономить память на инстанцирование шаблонов (функции придется спрятать в классы, наследующие реализацию обобщенных функций через void*) и пригодится для реализации мультиметодов.
template <template<typename _> class M> M<char> inc(char c) { return mreturn<M,char>(c+1); }
Достаточно простая функция, использующая монаду.
На Haskell она вызлядит
inc :: (Monad m) => Char -> m Char
inc c = return (succ c)
return здесь обозначает совсем другое, чем в C++.
А теперь перейдем к реализации монады IO. Объекты, с которыми работает монадный интерфейс в данном случае — операции вводв-вывода. В Haskell это обычные величины, в C++ они будут моделироваться классами.
#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();
}
};
Метод run выполняет эту операцию (в Haskell фактически он вызывается runtime-системой у объекта main).
Класс-контейнер IOm нужен, что бы спрятать тип операции, который может быть переменного размера.
Как мы видим, эти классы ни что, кроме названия, с монадами не связывает и они про монады ни чего не знают. Это важное преимущество классов типов перед обычными классами, которые должны знать свой интерфейс.
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; };
А вот две конкретные операции ввода-вывода — получить символ со стандартного ввода и вывести символ на стандартный вывод. А так же функция, которая превращает символ в операцию, которая его выводит.
template<typename v> class mconst: public IOop<v> {
v r;
public:
mconst(v x) {
r=x;
}
virtual v run() {
return r;
}
};
Этот класс реализует монадическую операцию «return», которая в данном случае создает операцию ввода-вывода, которая всегда «вводит» константу.
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;
}
};
А эта операция ">>=", которая сцепляет монаду с генератором новой монады.
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(v x) { IOm<v> r(new mconst<v>(x)); return r; }
};
А вот и самое главное — специализация реализации монады для IO.
template<typename i> IOm<unit> ignNL(i v) {
return bind<IOm,unit,char>(mreturn<IOm,char>('n'),putChar);
}
Это генератор IO, который игнорирует результат предыдущей монады и печатает 'n'.
ign :: a -> IO ()
ign _ = putChar 'n'
Для IO (и некоторых других монад, например парсеров) это игнорирование предыдущей монады достаточно популярная операция и для нее есть функция:
(>>) :: (Monad m) => m a -> m b -> m b
a >> b = a >>= _ -> b
А теперь проверим, как все это работает:
bind<IOm,unit,unit>(bind<IOm,unit,char>(bind<IOm,char,char>(getChar,inc),putChar),ignNL<unit>).run();
Мы читаем со стандартного ввода символ, его инкрементируем, печатаем, и печатаем перевод строки.
А теперь реализуем интерфейс монады для другого класса, который знает о монадах еще меньше.
#include<vector>
template<typename v> class myvector: public std::vector<v> { };
К сожалению, шаблон std::vector имеет два параметра (второй отвечает за политику аллокации и может подставляться поумолчанию). Современный gcc не позволяет его передавать в шаблон, который ждет шаблон с одним параметром (если мне память не изменяет, раньше таких строгостей не было). По этому приходится создавать простую обертку.
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(v x) {
myvector<v> e;
e.push_back(x);
return e;
}
};
Функциональность монады std::vector аналогична функциональности монады List в Haskell.
Пробуем, как это работает:
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;
}
Для подобной функциональности было бы достаточно класса типов «функтор», но мне не хотелось придумывать более сложный пример.
Автор: potan
