Привет
Когда-то, уже довольно давно, я поднимал здесь тему монад. Тогда я хотел получить монаду как некий интерфейс. Ничего стоящего из этого не получилось, и вот теперь, проанализировав ошибки, я готов нанести ответный удар. Теперь мне представляется, что основной моей ошибкой было забыть, что монада, помимо интерфейса — это ещё и контейнер. К сожалению, чтобы скрестить эти две абстракции, нужно иметь механизм типа virtual template function и, возможно, несколько более мощную систему типов, чем имеется в С++. Например, как в Haskell
Но не всё так плохо, в шаблонном программировании и интерфейсы и контейнеры реализуются с помощью одного механизма — параметров шаблонов — его и применим. Кто не хочет читать "многа букоф", может сразу посмотреть на
целый проект. Итак. Сначала опишем интерфейсную часть:
template <class A>
struct AssertIsMonad
{
typedef typename A::MonadT Result;
};
template <class MonadAdapter>
struct Monad
{
typedef Monad<MonadAdapter> MonadInterfaceT;
template <class A>
struct Return
{
typedef typename MonadAdapter::MonadImplementationT::template Return<A>::Result Result;
typedef typename AssertIsMonad<Result>::Result CheckOutData;
};
template <class A, class Func>
struct Bind
{
typedef typename AssertIsMonad<A>::Result CheckInData;
typedef typename MonadAdapter::MonadImplementationT::template Bind<A, Func>::Result Result;
typedef typename AssertIsMonad<Result>::Result CheckOutData;
};
};
Обратите внимание, вместо частичной специализации для проверки входных данных я применил механизм ассертов. По секрету скажу, что на 99% эти предосторожности излишни, в случае неправильных данных с большой вероятностью не будет работать и так — здесь ассерты имеют больше декоративный или документирующий характер. Продолжим. Здесь у нас определены две основные функции: return, кладущая элемент в контейнер, и bind, применяющая к элементам контейнера задаваемую функцию. Но просто монада в чисто виде — это скучно, определим производный класс, который потом и даст нам список:
template <class MonadAdapter>
struct MonadPlus : public Monad<MonadAdapter>
{
typedef MonadPlus<MonadAdapter> MonadInterfaceT;
struct MZero
{
typedef MonadAdapter MonadT;
};
template <class A, class B>
struct MPlus
{
typedef typename AssertIsMonad<A>::Result CheckInDataA;
typedef typename AssertIsMonad<B>::Result CheckInDataB;
typedef typename Util::If<Util::Same<MZero, A>::value,
B,
typename Util::If<Util::Same<MZero, B>::value,
A,
typename MonadAdapter::MonadImplementationT::template MPlus<A, B>::Result>::Result>::Result Result;
typedef typename AssertIsMonad<Result>::Result CheckOutData;
};
};
Здесь у нас задан нулевой элемент и функция сложения.
Рассмотрим теперь контейнерную часть — реализацию списка типов:
template <class TMonadAdapter>
struct ListBase
{
typedef ListBase<TMonadAdapter> MonadImplementationT;
typedef typename TMonadAdapter::MonadInterfaceT::MZero Nil;
template <class THead, class TTail>
struct Impl : public Nil
{
typedef THead HeadT;
typedef TTail TailT;
};
template <class T>
struct AssertIsList
{
typedef typename InnerImpl::AssertIsListImpl<T, ListBase<TMonadAdapter> >::Result Result;
};
template <class A>
struct Return
{
typedef Impl<A, Nil> Result;
typedef typename AssertIsList<Result>::Result CheckOutData;
};
template <class A, class B>
struct MPlus
{
typedef typename AssertIsList<A>::Result CheckInDataA;
typedef typename AssertIsList<B>::Result CheckInDataB;
typedef typename InnerImpl::ListConcateImpl<A, B, ListBase<TMonadAdapter> >::Result Result;
typedef typename AssertIsList<Result>::Result CheckOutData;
};
template <class A, class Func>
struct Bind
{
typedef typename AssertIsList<A>::Result CheckInData;
typedef typename InnerImpl::ListBindImpl<A, Func, ListBase<TMonadAdapter> >::Result Result;
typedef typename AssertIsList<Result>::Result CheckOutData;
};
};
namespace InnerImpl
{
template <class A, class B, class TListImpl>
struct ListConcateImpl
{
typedef typename TListImpl::template Impl<typename A::HeadT, typename ListConcateImpl<typename A::TailT, B, TListImpl>::Result> Result;
};
template <class B, class TListImpl>
struct ListConcateImpl<typename TListImpl::Nil, B, TListImpl>
{
typedef B Result;
};
template <class A, class Func, class TListImpl>
struct ListBindImpl
{
typedef typename ListConcateImpl<typename Func::template Proceed<typename A::HeadT>::Result,
typename ListBindImpl<typename A::TailT, Func, TListImpl>::Result,
TListImpl>::Result Result;
};
template <class Func, class TListImpl>
struct ListBindImpl<typename TListImpl::Nil, Func, TListImpl>
{
typedef typename TListImpl::Nil Result;
};
template <class T, class TList>
struct AssertIsListImpl
{
typedef typename Util::StaticAssert<Util::Same<T, typename TList::template Impl<typename T::HeadT, typename T::TailT> >::value>::Result Result;
};
template <class TList>
struct AssertIsListImpl<typename TList::Nil, TList>
{
typedef typename Util::StaticAssert<true> Result;
};
}
Как видно, реализация списка типов вполне стандартная. Единственная тонкость — из-за строгой стратегии вычислений приходится прибегать к частичной специализации, чтобы избежать бесконечного зацикливания.
Теперь самое интересное — как объединить эти две части. Для этого применим специальный шаблон — мост:
template <template <class> class TMonad, template <class> class TImpl>
struct Bridge
{
typedef typename TMonad< Bridge<TMonad, TImpl> >::MonadInterfaceT MonadInterfaceT;
typedef typename TImpl< Bridge<TMonad, TImpl> >::MonadImplementationT MonadImplementationT;
};
typedef MonadPlus< Bridge<MonadPlus, ListBase> > MonadList;
typedef ListBase< Bridge<MonadPlus, ListBase> > ListSpec;
MonadList — основной интерфейс, через который будем работать со списком. ListSpec используется, чтобы убрать палки, который нам вставляет в колёса редиска-компилятор gcc 3.4.5, на котором я всё это хозяйство тестировал.
Для тех, кто любит погорячее, покажу, как можно обойтись без шаблона Bridge:
template <template <class> class MonadAdapterTempl>
struct List : public ListBase< MonadAdapterTempl< List<MonadAdapterTempl> > >
{
};
typedef MonadPlus< List<MonadPlus> > MonadList;
typedef List<MonadPlus> ListSpec;
Теперь для примера попробуем написать для того, что получилось, оператор неподвижной точки и с его помощью погонять классический пример — вычисление факториала:
template <class Arg, class FPFunc>
struct FixedPointIterator
{
typedef typename MonadList::template Return<Arg>::Result MArg;
typedef typename FPFunc::template Rebind<Arg>::Result StepResult;
typedef typename MonadList::template Return<StepResult>::Result MStepResult;
typedef typename MonadList::MPlus<MArg,
typename MonadList::template Bind<MStepResult,
FPFunc
>::Result
>::Result Result;
};
template <class FPFunc>
struct FixedPointIterator<MonadList::MZero, FPFunc>
{
typedef typename MonadList::MZero Result;
};
template <class Func>
struct FixedPoint
{
template <class Arg>
struct Rebind
{
typedef typename Func::template Proceed<Arg>::Result Result;
};
template <class Arg>
struct Proceed
{
typedef typename FixedPointIterator<Arg, FixedPoint<Func> >::Result Result;
};
};
template <int i>
struct Int2Type
{
enum { value = i };
static void Print()
{
std::cout << value;
}
};
#define MListInt(x) typename MonadList::template Return< Int2Type<x> >::Result
template <int i, int j>
struct FactorialStepProceed
{
typedef typename MonadList::template MPlus<MListInt(i-1), MListInt(i*j)>::Result Result;
};
template <int j>
struct FactorialStepProceed<0, j>
{
typedef MonadList::MZero Result;
};
#define LISTSPEC(x,y) ListSpec::template Impl< x , y >
struct FactorialStep
{
template <class T>
struct Proceed;
};
template <class T, class U>
struct FactorialStep::Proceed< LISTSPEC(T, U) >
{
enum { i = T::value, j = U::HeadT::value };
typedef typename FactorialStepProceed<i, j>::Result Result;
};
...
#define MLInt(x) MonadList::Return< Int2Type<x> >::Result
typedef MonadList::Return<MonadList::MPlus<MLInt(6), MLInt(1)>::Result>::Result LFactInit;
typedef MonadList::Bind<LFactInit, FixedPoint<FactorialStep> >::Result LFactResult;
LFactResult будет содержать список ((6,1),(5,6),(4,30),(3,120),(2,360),(1,720),(0,720)).
Спасибо за внимание
В проекте, на который я дал ссылку выше, есть ещё и монада Maybe.
ЗЫ. Тому, кто хочет спросит, где такое применяется, и зачем нужно, отвечу словами кота Матроскина: "а ещё я на машинке умею и крестиком..."
Курица — это инструмент, с помощью которого одно яйцо производит другие.