Привет Когда-то, уже довольно давно, я поднимал здесь тему монад. Тогда я хотел получить монаду как некий интерфейс. Ничего стоящего из этого не получилось, и вот теперь, проанализировав ошибки, я готов нанести ответный удар. Теперь мне представляется, что основной моей ошибкой было забыть, что монада, помимо интерфейса — это ещё и контейнер. К сожалению, чтобы скрестить эти две абстракции, нужно иметь механизм типа 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.

ЗЫ. Тому, кто хочет спросит, где такое применяется, и зачем нужно, отвечу словами кота Матроскина: "а ещё я на машинке умею и крестиком..."