Re[5]: Монады в C++
От: Кодт Россия  
Дата: 21.09.07 12:44
Оценка: 12 (1)
Здравствуйте, frogkiller, Вы писали:

К>>Maybe как модель вычислений — это, практически, try-catch.
F>Это понятно, остальные в принципе тоже имеют не сильно сложную модель вычислений.

Ну не скажи.
Большинство случаев — это линейные вычисления, а List — это комбинаторный взрыв На нём (благодаря ленивости) можно сделать, например, вычисления с откатами — то, что в других случаях требует MonadPlus.

К>>А вот как контейнер — как модель трансформации содержимого в монаду и обратно — вот это интересно.
F>Именно. А ещё интересно взаимодействие между монадами.

К>>К чёрту реинтерпреты! Ты не с того конца начал: на питоне, с его рантайм-типизацией, была жалкая симуляция хаскельных монад.
F>Собственно у меня изначальный вопрос такой и был как обойтись статикой.

К>>Тут нужно использовать либо типизацию в compile time, либо (а скорее всего, вместе) то, как в хаскеле сделан рантайм и полиморфные методы.
F>А как в хаскеле это сделано? Я читал про его полиморфизм, что называется, офигел мрачно, и отложил хаскель до лучших времён.

В хаскеле есть
— структуры (объявленные как типы данных — data, type, newtype) (передаваемые по обезличенному ленивому указателю)
— и таблицы функций (объявленные как классы типов — class). Эти таблицы передаются отдельно.

Там, где компилятор знает конкретный тип — он подсовывает в вызываемые функции таблицы для этого типа.
Там, где известны лишь общие сведения, — таблицы берутся как аргументы функции и передаются дальше.

Но это, так сказать, для внутреннего пользования.
Альтернативой такой механике является экспорт шаблонов.



Очень хочется, конечно, воплотить монады "по-честному".
Т.е. (>>=) реализовать через Functor, x>>=y =join(fmap y x)
Но это очень запаристо, поскольку придётся тащить карринг и прочее.

Но вот навскидку. Не компилировал ещё.
template<class T> struct maybe
{
    bool is_just;
    T value;
    
    maybe() : is_just(false) {}
    explicit maybe(T v) : is_just(true), value(v) {}
    
    static maybe just(T v) { return maybe(v); }
    static maybe nothing() { return maybe(); }
};

template<class T> struct list
{
    std::list<T> values;
};


template<template<class>class M, class A, class B>
M<B> operator =>> (M<A> ma, function< M<B>(*)(A) > f)
{
    return join(fmap(f)(ma));
}





template<class A, class B>
function<maybe<A>(*)(maybe<B>)> fmap(function<A(*)(B)> f)
{
    return bind(maybe<A>::just, bind(f, _1));
}
template<class A>
maybe<A> join(maybe<maybe<A> > mma)
{
    return mma.is_just ? maybe<A>::just(mma.value) : maybe<A>::nothing();
}
template<class A>
maybe<A> return_(A x)
{
    return maybe<A>::just(x);
}
template<class A>
maybe<A> fail()
{
    return maybe<A>::nothing();
}






template<class A, class B>
static list<A> map(function<A(*)(B)> f, list<B> const& xs)
{
    list<A> ys; transform(xs.values.begin(), xs.values.end(), back_inserter(ys.values), f);
    return ys;
}


template<class A, class B>
function<list<A>(*)(list<B>)> fmap(function<A>(*)(B) f)
{
    return bind(map<A,B>, f, _1);
}
template<class A>
list<A> join(list<list<A> > xss)
{
    list<A> xs;
    for_each(xss.values.begin(), xss.values.end(), bind(mem_fun(&std::list<A>::append), ref(xs.values), _1));
    return xs;
}
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[7]: Монады в C++
От: Кодт Россия  
Дата: 21.09.07 15:53
Оценка: 12 (1)
Здравствуйте, frogkiller, Вы писали:

F>Хм... ленивость реализуется через замыкания, замыкания — через функторы. Получается, что в с++ вполне можно добиться ленивости, при этом даже нельно извращаясь

Не всё так просто!
Ленивость должна вычисляться единожды.
Будет что-то этакое
template<class T>
class Lazy
{
    function<T(*)()> e_;
    
    static T id(T v) { return v; }
    
    template<class E>
    static T force(E e)
    {
        T v = e();
        e_ = bind(id, v);
        return v;
    }
public:
    // вычисленное значение
    Lazy(T v) : e_( bind(id, v) ) {}
    
    // ленивое значение
    template<class E>
    Lazy(E e) : e_( bind(&Lazy::force, this, e) ) {}
    
    T operator() const { return e_(); }
};




К>>Очень хочется, конечно, воплотить монады "по-честному".
К>>Но это очень запаристо, поскольку придётся тащить карринг и прочее.

F>но иначе, боюсь, бесполезно

Да, в принципе, не обязательно. Карринг — это лишь отчасти фундамент, а отчасти просто сахар.
Можно каррингом заниматься только там, где он реально требуется, а в остальных местах пусть будут кортежи аргументов на уровне языка, как обычно.
К>>template<template<class>class M, class A, class B>
К>>M<B> operator =>> (M<A> ma, function< M<B>(*)(A) > f)
К>>{
К>>    return join(fmap(f)(ma));
К>>}

F>Я правильно понимаю, что эта операция извлекает содержимое монады, что-то такое с ним делает, и кладёт обратно?
F>Т.е. контейнер с его свойствами остаётся прежним, меняется лишь наполнение.

Именно.
Причём >>= оказалось можно выразить через более общий класс, Functor.
(>>=) :: Monad m => m a -> (a -> m b) -> m b
-- на входе:
--   монада (m a)
--   функция, для каждого элемента (a) порождающая свою монаду (m b)
-- на выходе:
--   монада (m b), являющаяся объединением результатов функии

ma >>= amb =
    let
        mammb = fmap amb -- a -> m b превратили в m a -> m m b
        mmb = mammb ma -- подали m a, вернули m m b
        mb = join mmb -- переупаковали
    in mb


К>>template<class A, class B>
К>>function<maybe<A>(*)(maybe<B>)> fmap(function<A(*)(B)> f)
К>>{
К>>    return bind(maybe<A>::just, bind(f, _1));
К>>}

F>А по аналогии с предыдущим не получится обобщение?
F>
F>template<template<class>class M, class A, class B>
F>function<M<A>(*)(M<B>)> fmap(function<A(*)(B)> f)
F>{
F>    return bind(M<A>::construct, bind(f, _1));  // construct - фабричный метод для создания класса, по сути конструктор
F>                                                // признаться, я плохо понимаю, что делает получившаяся конструкция
F>}
F>

Нет, не получится. Потому что fmap такого вида подходит только для монад, содержащих единственный элемент: Id, Maybe.
Кстати, я малость напутал: забыл распаковку.
template<class A> maybe<A> just(A a) { return maybe<A>(a); }

template<class A> A from_just(maybe<A> ma)
{
    if(!ma.ok) throw runtime_error("распаковка из Nothing");
    return ma.value;
}

template<class A, class B>
function< maybe<A>(*)(maybe<B>) > fmap( function<A(*)(B)> f)
{
    return bind(just<A>, bind(f, bind(from_just<B>, _1)));
}

Для списка, очевидно, нужно не bind(enlist, bind(f, bind(fromlist, _1))), а сделать функцию, которая
— принимает на вход список
— к каждому элементу этого списка применяет f
— и возвращает список результатов.

bind'ы же
— принимают на вход упакованное значение _1
— применяют распаковщик, получая одно распакованное значение
— к нему применяют f, получая один результат
— и к нему уже применяют упаковщик

А для монады State, которая вообще тащит функцию... Лучше тебе книжку по Хаскелю почитать 

К>>template<class A>
К>>maybe<A> join(maybe<maybe<A> > mma)
К>>{
К>>    return mma.is_just ? maybe<A>::just(mma.value) : maybe<A>::nothing();
К>>}

F>А вот это я совсем не понимаю (как и следующий join(list<list<A>>)). То есть я понимаю, что она делает как некая последовательность действий, но совсем не понимаю почему надо именно так. Это какое-то эмпирическое наблюдение или есть какая-то технология?

Это устраняется лишняя косвенность. Maybe (Maybe a) превращается в Maybe a.
Очевидно, Nothing --> Nothing, Just Nothing --> Nothing, Just (Just x) --> Just x.

Аналогично со списками. List (List a) --> List a.
Просто берём и склеиваем все списки.

F>И как тогда должна выглядеть f, например, в случае сложения (как у меня в примере)? Я написал интуитивно
F>Если не трудно, объясни, пожалуйста, "на пальцах"

Эта процедура называется лифт — когда из обычной функции получается монадная.
liftM :: Monad m => (a -> b) -> (m a -> m b)
liftM f ma = ma >>= (\a -> f a)

liftM2 :: Monad m => (a -> b -> c) -> (m a -> m b -> m c)
liftM2 f ma mb = ma >>= (\a -> (mb >>= \b -> f a b))

liftM — то же самое, что fmap.
liftM2 — эх, запаристо...
template<template<class>class M, class A, class B, class C>
function<M<C>(*)(M<A>,M<B>)> liftM2(function<C(*)(A,B)> f)
{
    // \a -> (mb >>= \b -> f a b)
    function<M<C>(*)(A,M<B>)> f1 = bind(pass<B,C>, _2 /*mb*/, bind(f, _1 /*a*/)/*(b)*/);
    return bind(pass<A,C>, _1/*ma*/, bind(f1, _2/*mb*/)/*(a)*/
}


int x = from_just( liftM2<Maybe,int,int>(operator+) (just<int>(1), just<int>(2)) );

Кажется, так.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Монады в C++
От: frogkiller Россия  
Дата: 20.09.07 14:03
Оценка:
В статье в LinuxJournal приводится оригинальная интерпретация одной из концепций ФП — монад. Но все примеры были на языках, поддерживающих замыкания. В ожидании С++0х со встроенной их поддержкой попробовал переписать примеры "руками". Извиняюсь за обилие кода, меньше не получилось 

#include <iostream>

template <typename TValue>
class CMonad;

template <typename TValue>
class CMonad
{
public:
    typedef CMonad<TValue> TRetInst;
    typedef TValue           TArgInst;

protected:
    TValue m_value;
    CMonad() {}

public:
    struct CMyFunctor
    {
        virtual TRetInst * apply(const TArgInst &) = 0;
    };

    CMonad(const TValue &_value) : m_value(_value) {}

    virtual TRetInst * pass(CMyFunctor * pfn)
    {
        return pfn->apply(m_value);
    }

    virtual ~CMonad() {}

    virtual void Print() const = 0;
};

template <class TValue>
struct IArithmetic
{
    typedef CMonad<TValue> TRetInst;

    template <typename TInstance>
    class CAddFunctor : public CMonad<TValue>::CMyFunctor
    {
        const TValue & m_value;
    public:
        CAddFunctor(const TValue &_value) : m_value(_value) {}
        virtual TRetInst * apply(const TValue &_value)
        {
            return new TInstance(m_value + _value);
        }
    };

    template <template <typename> class CApplication, typename TInstance>
    class CMyBinder : public CMonad<TValue>::CMyFunctor
    {
        TRetInst * m_value;
    public:
        CMyBinder(TRetInst * _value) : m_value(_value) {}
        virtual TRetInst * apply(const TValue &_value)
        {
            CApplication<TInstance> app(_value);
            return m_value->pass(&app);
        }
    };

    template <typename TInstance>
    IArithmetic<TValue> * Add(TInstance &rhs)
    {
        CMyBinder<CAddFunctor, TInstance> app(dynamic_cast<TRetInst *>(&rhs));
        return dynamic_cast<IArithmetic<TValue> *>(dynamic_cast<CMonad<TValue>*>(this)->pass(&app));
    }
    virtual ~IArithmetic() {}
};

template <typename TValue, typename TInstance>
class CMaybe : public CMonad<TValue>
{
    bool m_bNone;

public:
    struct None {};
    static None & getNone()
    {
        static None none;
        return none;
    }

    typedef CMonad<TValue> IParent;

    CMaybe(const TValue &_value) : IParent(_value), m_bNone(false) {}
    CMaybe(const None &) : m_bNone(true) {}

    virtual typename IParent::TRetInst * pass(typename IParent::CMyFunctor * pfn)
    {
        if (m_bNone)
        {
            return new TInstance(getNone());
        }
        return IParent::pass(pfn);
    }

    virtual void Print() const
    {
        if (m_bNone)
        {
            std::cout << "Maybe(none)" << std::endl;
        }
        else
        {
            std::cout << "Maybe(" << this->m_value << ")" << std::endl;
        }
    }
};

template <typename TValue, typename TInstance>
class CMaybe2 : public CMonad<TValue>
{
    bool m_bNone;

public:
    struct None {};
    static None & getNone()
    {
        static None none;
        return none;
    }

    typedef CMonad<TValue> IParent;

    CMaybe2(const TValue &_value) : IParent(_value), m_bNone(false) {}
    CMaybe2(const None &) : m_bNone(true) {}

    virtual typename IParent::TRetInst * pass(typename IParent::CMyFunctor * pfn)
    {
        if (m_bNone)
        {
            return new TInstance(TValue());
        }
        return IParent::pass(pfn);
    }

    virtual void Print() const
    {
        std::cout << "Maybe(" << this->m_value << ")" << std::endl;
    }
};

template <typename T>
struct CArithmeticMaybe : public CMaybe<T, CArithmeticMaybe<T> >, public IArithmetic<T>
{
    typedef CMaybe<T, CArithmeticMaybe<T> > CMaybeParent;
    CArithmeticMaybe(const typename CMaybeParent::None &none) : CMaybeParent(none) {}
    CArithmeticMaybe(const T &_value) : CMaybeParent(_value) {}
};

template <typename T>
struct CArithmeticMaybe2 : public CMaybe2<T, CArithmeticMaybe2<T> >, public IArithmetic<T>
{
    typedef CMaybe2<T, CArithmeticMaybe2<T> > CMaybeParent;
    CArithmeticMaybe2(const typename CMaybeParent::None &none) : CMaybeParent(none) {}
    CArithmeticMaybe2(const T &_value) : CMaybeParent(_value) {}
};

typedef CArithmeticMaybe<int> CMaybeInt;
typedef CArithmeticMaybe2<int> CMaybeInt2;

CMaybeInt n1(5), n2(6), n3(CMaybeInt::getNone());
CMaybeInt2 m1(5), m2(6), m3(CMaybeInt2::getNone());

int main(int argc, char* argv[])
{
    dynamic_cast<CMonad<int>*>(n1.Add(n2)->Add(n2))->Print();
    dynamic_cast<CMonad<int>*>(n1.Add(n2)->Add(n3))->Print();

    std::cout << "--------------------" << std::endl;
    dynamic_cast<CMonad<int>*>(m1.Add(m2)->Add(m2))->Print();
    dynamic_cast<CMonad<int>*>(m1.Add(m2)->Add(m3))->Print();
    dynamic_cast<CMonad<int>*>(m3.Add(m2)->Add(m1))->Print();

    // все ухищрения с dynamic_cast ради вот такой возможности
    // связывать монады разных типов
    std::cout << "--------------------" << std::endl;
    dynamic_cast<CMonad<int>*>(m1.Add(n2)->Add(m3))->Print();
    dynamic_cast<CMonad<int>*>(m1.Add(m2)->Add(n2))->Print();
    dynamic_cast<CMonad<int>*>(m3.Add(n2)->Add(m2))->Print();

    return 0;
}


Что мне не нравится:
1. Приходится постоянно выносить действительное имя класса в качестве шаблонного параметра, чтобы иметь возможность создавать объект нужного класса.
2. Чтобы связывать монады разных типов, приходится постоянно использовать dynamic_cast.

Профи буста, подскажите, пожалуйста, можно ли добиться аналогичного эффекта в статике? А главное, как это сделать...

PS. Про утечку памяти можно мне не объяснять, я и сам знаю, где она появляется, и как это лечится.
PPS. Подозреваю, что изобрёл велоспед, и если это так, не пинайте слишком сильно
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Re: Монады в C++
От: Кодт Россия  
Дата: 20.09.07 16:18
Оценка:
Здравствуйте, frogkiller, Вы писали:

F>В статье в LinuxJournal приводится оригинальная интерпретация одной из концепций ФП — монад. Но все примеры были на языках, поддерживающих замыкания. В ожидании С++0х со встроенной их поддержкой попробовал переписать примеры "руками". Извиняюсь за обилие кода, меньше не получилось

Если уж тестировать свои руки, то не на Maybe, а сразу на List. У него более затейливые bind и join.

F>Что мне не нравится:
F>1. Приходится постоянно выносить действительное имя класса в качестве шаблонного параметра, чтобы иметь возможность создавать объект нужного класса.

Ну и нормально, тип Maybe ведь параметризован типом элемента.
А вот класс Monad параметризуется шаблоном типа, — это challenge, как на С++ выразить наиболее общо.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[2]: Монады в C++
От: frogkiller Россия  
Дата: 21.09.07 08:10
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Если уж тестировать свои руки, то не на Maybe, а сразу на List. У него более затейливые bind и join.

Не, чтобы тестировать руки на List'e, надо понимать, как там внутри что устроено. Я три раза переписал Maybe (предыдущий вариант ты видел в "Философии", он без RTI, но в нём не проходят связки с монадами разных типов), прежде чем начал хоть немного догадываться, как он работает. (Очень подозреваю, что проблема больше частью в области психологии и восприятия — то, что в ФП считается тривиальным, с одной стороны можно лего объяснить на пальцах, но с другой — при попытке сделать то же самое на императивном С++ с жёсткой типизацией — наступает ступор.)
Надеюсь, когда-нибудь руки дойдут и до более сложных конструкций.

F>>Что мне не нравится:
F>>1. Приходится постоянно выносить действительное имя класса в качестве шаблонного параметра, чтобы иметь возможность создавать объект нужного класса.

К>Ну и нормально, тип Maybe ведь параметризован типом элемента.
К>А вот класс Monad параметризуется шаблоном типа, — это challenge, как на С++ выразить наиболее общо.

Имхо это выглядит сильно корявым. Понятно, что здесь напрашивается аналогия с дотнетовскими метаданными, с помощью которых "лёгким движением руки" можно получить нужный тип, но хотелось как-нибудь этого избежать. Сначала я подумал, что может помочь виртуальный Clone(), но тогда придётся передавать указатель на объект во все методы, что по сути ничем не лучше выноса типа в параметр шаблона.
Другой, менее очевидный аспект:
template <typename TInstance>
IArithmetic<TValue> * Add(TInstance &rhs) {...}

и последующее ->Add(m2)...

Получается, что тип элемента, задаваемый TInstance, который потом протянется по цепочке шаблонов, определяется типом m2. А разве это то, что нам нужно? При таком подходе будет облом, если соединять монады, производные от IArithmetic и какого-нибудь IAnotherArithmetic, даже если они оба будут потомками одного класса, dynamic_cast от одного к другому вернёт 0.
Возможно, решение надо искать в виде:
template <typename TInstance>
IArithmetic<TValue> * Add(TRetInst &rhs) {...}

и явно указывать тип элемента ->Add<CMaybeInt>(m2)...
Но это как минимум не красиво, и я не уверен в корректности работы такой конструкции.

Другой вариант — отказаться от RTI и шаманить с reinterpret_cast'ами, но это решение мне нравится ещё меньше, потому как накладывает сильные ограничения на получившуюся систему.

В общем понятно, что задача с наскока не решается, а дольше пяти минут над ней никто здесь думать не будет. А так, получается неплохое задание для какого-нибудь конкурса.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Re[3]: Монады в C++
От: Кодт Россия  
Дата: 21.09.07 09:18
Оценка:
Здравствуйте, frogkiller, Вы писали:

К>>Если уж тестировать свои руки, то не на Maybe, а сразу на List. У него более затейливые bind и join.

F> Не, чтобы тестировать руки на List'e, надо понимать, как там внутри что устроено. Я три раза переписал Maybe (предыдущий вариант ты видел в "Философии", он без RTI, но в нём не проходят связки с монадами разных типов), прежде чем начал хоть немного догадываться, как он работает.

Без понимания — смысла нет.
Maybe как модель вычислений — это, практически, try-catch.
А вот как контейнер — как модель трансформации содержимого в монаду и обратно — вот это интересно.

F> (Очень подозреваю, что проблема больше частью в области психологии и восприятия — то, что в ФП считается тривиальным, с одной стороны можно лего объяснить на пальцах, но с другой — при попытке сделать то же самое на императивном С++ с жёсткой типизацией — наступает ступор.)

Ну, в хаскелле типизация пожёстче будет, чем в С++

F>Надеюсь, когда-нибудь руки дойдут и до более сложных конструкций.



F>Получается, что тип элемента, задаваемый TInstance, который потом протянется по цепочке шаблонов, определяется типом m2. А разве это то, что нам нужно? При таком подходе будет облом, если соединять монады, производные от IArithmetic и какого-нибудь IAnotherArithmetic, даже если они оба будут потомками одного класса, dynamic_cast от одного к другому вернёт 0.
F>Возможно, решение надо искать в виде:
F>
F>template <typename TInstance>
F>IArithmetic<TValue> * Add(TRetInst &rhs) {...}
F>

F>и явно указывать тип элемента ->Add<CMaybeInt>(m2)...
F>Но это как минимум не красиво, и я не уверен в корректности работы такой конструкции.

F>Другой вариант — отказаться от RTI и шаманить с reinterpret_cast'ами, но это решение мне нравится ещё меньше, потому как накладывает сильные ограничения на получившуюся систему.

F>В общем понятно, что задача с наскока не решается, а дольше пяти минут над ней никто здесь думать не будет. А так, получается неплохое задание для какого-нибудь конкурса.

К чёрту реинтерпреты! Ты не с того конца начал: на питоне, с его рантайм-типизацией, была жалкая симуляция хаскельных монад.

Тут нужно использовать либо типизацию в compile time, либо (а скорее всего, вместе) то, как в хаскеле сделан рантайм и полиморфные методы.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[4]: Монады в C++
От: frogkiller Россия  
Дата: 21.09.07 10:20
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Maybe как модель вычислений — это, практически, try-catch.

Это понятно, остальные в принципе тоже имеют не сильно сложную модель вычислений.

К>А вот как контейнер — как модель трансформации содержимого в монаду и обратно — вот это интересно.

Именно. А ещё интересно взаимодействие между монадами.

К>К чёрту реинтерпреты! Ты не с того конца начал: на питоне, с его рантайм-типизацией, была жалкая симуляция хаскельных монад.

Собственно у меня изначальный вопрос такой и был как обойтись статикой.

К>Тут нужно использовать либо типизацию в compile time, либо (а скорее всего, вместе) то, как в хаскеле сделан рантайм и полиморфные методы.

А как в хаскеле это сделано? Я читал про его полиморфизм, что называется, офигел мрачно, и отложил хаскель до лучших времён.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Re[2]: Монады в C++
От: 0xDEADBEEF Ниоткуда  
Дата: 21.09.07 13:09
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Если уж тестировать свои руки, то не на Maybe, а сразу на List. У него более затейливые bind и join.
Гм, если я правильно понял про монады (за полчаса чтения википедии и ссылок из нее), то "maybe" здорово похожа на boost::variant, если к нему прикрутить операторы.

например:
struct Nothing {};
typedef boost::variant<char,short,int,long,float,double,Nothing> Number;
Number operator/(Number const& a, Number const& b)
{
   //используем apply_visitor чтобы разрулить варианты деления для различных типов.
}


...Что касается List, то имхо, он здорово похож на tuple, в особенности в свете недавних пропозалов добавить к нему операции slice и concat
__________
16.There is no cause so right that one cannot find a fool following it.
Re[3]: Монады в C++
От: Кодт Россия  
Дата: 21.09.07 14:29
Оценка:
Здравствуйте, 0xDEADBEEF, Вы писали:

DEA>...Что касается List, то имхо, он здорово похож на tuple, в особенности в свете недавних пропозалов добавить к нему операции slice и concat

А как на tuple выразить list comprehensions?
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[6]: Монады в C++
От: frogkiller Россия  
Дата: 21.09.07 14:30
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Ну не скажи.
К>Большинство случаев — это линейные вычисления, а List — это комбинаторный взрыв На нём (благодаря ленивости) можно сделать, например, вычисления с откатами — то, что в других случаях требует MonadPlus.

Хм... ленивость реализуется через замыкания, замыкания — через функторы. Получается, что в с++ вполне можно добиться ленивости, при этом даже нельно извращаясь
По поводу List'а согласен. Именно поэтому мне кажется нечестным (да и неправильным) реализовывать его через стандартный.

К>


К>Очень хочется, конечно, воплотить монады "по-честному".

ага

К>Т.е. (>>=) реализовать через Functor, x>>=y =join(fmap y x)
К>Но это очень запаристо, поскольку придётся тащить карринг и прочее.

но иначе, боюсь, бесполезно

К>template<template<class>class M, class A, class B>
К>M<B> operator =>> (M<A> ma, function< M<B>(*)(A) > f)
К>{
К> return join(fmap(f)(ma));
К>}

Я правильно понимаю, что эта операция извлекает содержимое монады, что-то такое с ним делает, и кладёт обратно?
Т.е. контейнер с его свойствами остаётся прежним, меняется лишь наполнение.

К>template<class A, class B>
К>function<maybe<A>(*)(maybe<B>)> fmap(function<A(*)(B)> f)
К>{
К> return bind(maybe<A>::just, bind(f, _1));
К>}

А по аналогии с предыдущим не получится обобщение?
template<template<class>class M, class A, class B>
function<M<A>(*)(M<B>)> fmap(function<A(*)(B)> f)
{
    return bind(M<A>::construct, bind(f, _1));  // construct - фабричный метод для создания класса, по сути конструктор
                                                // признаться, я плохо понимаю, что делает получившаяся конструкция
}


К>template<class A>
К>maybe<A> join(maybe<maybe<A> > mma)
К>{
К> return mma.is_just ? maybe<A>::just(mma.value) : maybe<A>::nothing();
К>}

А вот это я совсем не понимаю (как и следующий join(list<list<A>>)). То есть я понимаю, что она делает как некая последовательность действий, но совсем не понимаю почему надо именно так. Это какое-то эмпирическое наблюдение или есть какая-то технология?
Я догадываюсь, что второй порядок у шаблона появляется потому, что в действительности fmap выглядит как-то так:
template<template<class>class M2, template<class>class M1, class A, class B>
function<M2<M1<A>>(*)(M2<B>)> fmap(function<M1<A>(*)(B)> f)
{
    return bind(M2<M1<A>>::construct, bind(f, _1));
}

И как тогда должна выглядеть f, например, в случае сложения (как у меня в примере)? Я написал интуитивно
template<template<typename> class M, typename B, typename A>
M<B> my_add(const A &rhs, const A &lhs)
{
    return M<B>::construct((B)(rhs + lhs));
}

Но что с этим теперь делать?

Если не трудно, объясни, пожалуйста, "на пальцах"
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Re[8]: Монады в C++
От: frogkiller Россия  
Дата: 22.09.07 16:42
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Не всё так просто!
К>Ленивость должна вычисляться единожды.
К>Будет что-то этакое
К>[...]

Угу, красиво.



К>Именно.
К>Причём >>= оказалось можно выразить через более общий класс, Functor.
К>
К>(>>=) :: Monad m => m a -> (a -> m b) -> m b
К>-- на входе:
К>--   монада (m a)
К>--   функция, для каждого элемента (a) порождающая свою монаду (m b)
К>-- на выходе:
К>--   монада (m b), являющаяся объединением результатов функии

К>ma >>= amb =
К>    let
К>        mammb = fmap amb -- a -> m b превратили в m a -> m m b
К>        mmb = mammb ma -- подали m a, вернули m m b
К>        mb = join mmb -- переупаковали
К>    in mb
К>


С трудом, но понять можно. При 
(>>=) :: Monad m => m a -> (a -> m b) -> m b

join нужен для "восстановления размерности". При этом fmap не может быть вида (a -> b), потому что это не будет работать на сложных (списочных) структурах. Основная работа ложится на join, она по сути определяет "топологию" монады. Правильно?

F>>И как тогда должна выглядеть f, например, в случае сложения (как у меня в примере)? Я написал интуитивно
F>>Если не трудно, объясни, пожалуйста, "на пальцах"

К>Эта процедура называется лифт — когда из обычной функции получается монадная.
К>[...]
К>Кажется, так.

Я имел ввиду несколько другое. Лифт выдаёт ma -> mb. А тут a -> mb. Т.е. операция должна быть такая: (a -> b) -> (ma -> mb).
Обычная функция сложения выглядит так:
template <typename A>
A sum(const A &lhs, const A &rhs);

Усложним задачу, пусть она возвращает значение другого типа:
template <typename B, typename A>
B sum(const A &lhs, const A &rhs);

Это в принципе понятно, но не логично, зачем-то в функции объединили два различных действия: само сложение и тайпкаст.
И когда мы добавляем к тайпкасту ещё и оборачивание в монаду, получается совсем каша.



PS.
К>Лучше тебе книжку по Хаскелю почитать

Не встречал ни одной, где бы всё объяснялось человеческим языком. Везде сначала долго разжевывают, что такое лямбда-исчисление, как функцию можно передавать в качестве аргумента и другие "тривиальные вещи". Но мне (как, думаю, и большинству тут на форуме) в институте это уже успели довольно подробно рассказать. А затем в три абзаца, мол, есть такая штука — монада (в основном IO), применяется вот так. И всё. А вот теории групп и тд. у меня не было.
Написал бы ты сам что ли на досуге
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Re[8]: Монады в C++
От: Кодт Россия  
Дата: 24.09.07 09:16
Оценка:
К>Эта процедура называется лифт — когда из обычной функции получается монадная.

Я всё-таки забыл сделать лифт результатов. Исправляюсь:

К>liftM :: Monad m => (a -> b) -> (m a -> m b)
К>liftM f ma = ma >>= (\a -> return f a)

К>liftM2 :: Monad m => (a -> b -> c) -> (m a -> m b -> m c)
К>liftM2 f ma mb = ma >>= (\a -> (mb >>= \b -> return f a b))

К>liftM — то же самое, что fmap.
К>liftM2 — эх, запаристо...
К>template<template<class>class M, class A, class B, class C>
К>function<M<C>(*)(M<A>,M<B>)> liftM2(function<C(*)(A,B)> f)
К>{
К>    // \a -> (mb >>= \b -> f a b)
К>    function<M<C>(*)(A,M<B>)> f1 = bind(return_<M,C>, bind(pass<B,C>, _2 /*mb*/, bind(f, _1 /*a*/)/*(b)*/));
К>    return bind(pass<A,C>, _1/*ma*/, bind(f1, _2/*mb*/)/*(a)*/
К>}


К>int x = from_just( liftM2<Maybe,int,int>(operator+) (just<int>(1), just<int>(2)) );

К>Кажется, так.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[9]: Монады в C++
От: Кодт Россия  
Дата: 24.09.07 09:16
Оценка:
Здравствуйте, frogkiller, Вы писали:

F>С трудом, но понять можно. При
F>
F>(>>=) :: Monad m => m a -> (a -> m b) -> m b
F>

F>join нужен для "восстановления размерности". При этом fmap не может быть вида (a -> b), потому что это не будет работать на сложных (списочных) структурах. Основная работа ложится на join, она по сути определяет "топологию" монады. Правильно?

Совершенно верно.
Причём в реальности авторы библиотеки монад не напрягают компилятор фокусами с fmap/join, а сразу кодируют >>=. Потому что, хотя компилятор и умный, но зачем лишний раз его напрягать, если можно упростить.
Так,
instance Monad Id where
    x >>= f = f x
instance Monad Maybe where
    Nothing >>= _ = Nothing
    (Just x) >>= action = action x
instance Monad List where
    xs >>= action = foldr (++) [] (action xs) -- join и fmap

В случае List удобно использовать foldr, потому что работа со списками лежит в фундаменте ФП, и компилятор заточен под оптимизацию в терминах морфизмов списков.

F>>>И как тогда должна выглядеть f, например, в случае сложения (как у меня в примере)? Я написал интуитивно
F>>>Если не трудно, объясни, пожалуйста, "на пальцах"

К>>Эта процедура называется лифт — когда из обычной функции получается монадная.
К>>[...]
К>>Кажется, так.

F>Я имел ввиду несколько другое. Лифт выдаёт ma -> mb. А тут a -> mb. Т.е. операция должна быть такая: (a -> b) -> (ma -> mb).
Дык, смотри: лифт (a->m b) приводит к (m a -> m m b). А после этого нужно сделать join.

F>Обычная функция сложения выглядит так:
F>template <typename A> A sum(const A &lhs, const A &rhs);

F>Усложним задачу, пусть она возвращает значение другого типа:
F>template <typename B, typename A> B sum(const A &lhs, const A &rhs);

F>Это в принципе понятно, но не логично, зачем-то в функции объединили два различных действия: само сложение и тайпкаст.
F>И когда мы добавляем к тайпкасту ещё и оборачивание в монаду, получается совсем каша.

Остаётся только посоветовать не практиковать typecast без нужды
В Хаскеле (да и в других Хиндли-Милнеровских языках) он всегда делается явно, что очень быстро отбивает желание применять его там, где можно обойтись.
С другой стороны, typecast — это плоть и кровь С++. Так что ищи обходные пути.

Что касается sum, то — а какие проблемы? liftM2 поднимает и гетерогенные функции


Возможно, что стоит подумать в сторону monad comprehensions, а не в сторону теории групп.
plus :: a -> b -> b
plusM :: m a -> m b -> m b

-- для m == List, это выглядело бы так
plusM ma mb = [ plus a b | a <- ma, b <- mb ]

То есть, попробовать написать функцию for_each_M или что-то в таком роде.



F>PS.
К>>Лучше тебе книжку по Хаскелю почитать

F>Не встречал ни одной, где бы всё объяснялось человеческим языком. Везде сначала долго разжевывают, что такое лямбда-исчисление, как функцию можно передавать в качестве аргумента и другие "тривиальные вещи". Но мне (как, думаю, и большинству тут на форуме) в институте это уже успели довольно подробно рассказать. А затем в три абзаца, мол, есть такая штука — монада (в основном IO), применяется вот так. И всё. А вот теории групп и тд. у меня не было.
F>Написал бы ты сам что ли на досуге

Я начинал с Yet Another Haskell Tutorial — там монадам посвящено около половины книги. Причём не с позиций отвлечённых, а именно практика. Почему те или иные вещи превращаются в монады (что IO, что State, что List).
А сразу с теории категорий — смысла нет. Не к чему её будет применять.
Равно как и жалкие попытки показать "как сделать императивно через задницу в IO".
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[9]: Монады в C++
От: frogkiller Россия  
Дата: 24.09.07 14:38
Оценка:
Здравствуйте, Кодт, Вы писали:

К>
К>>template<template<class>class M, class A, class B, class C>
К>>function<M<C>(*)(M<A>,M<B>)> liftM2(function<C(*)(A,B)> f)
К>>{
К>>    // \a -> (mb >>= \b -> f a b)
К>>    function<M<C>(*)(A,M<B>)> f1 = bind(return_<M,C>, bind(pass<B,C>, _2, bind(f, _1 )));
К>>    return bind(pass<A,C>, _1, bind(f1, _2));
К>>}


К>>int x = from_just( liftM2<Maybe,int,int>(operator+) (just<int>(1), just<int>(2)) );
К>

К>>Кажется, так.

Всё равно не понятно (наверное, я сильно тупой ), объясни, пожалуйста, :
1. Что такое pass?

2. Вообще, правильно ли я понимаю работу bind:

Пусть f имеет тип function<C(*)(A,B)>.
Какой тип будет тогда у bind(f, _1) ? Или это расчёт на несуществующий карринг?

У меня компилятор ругается на такое:
int my_plus(int lhs, int rhs) { return lhs + rhs; }
(void)bind(my_plus, _1); // пять ошибок
(void)bind(my_plus, _1, _2); // ok
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Re[10]: Монады в C++
От: Кодт Россия  
Дата: 24.09.07 16:53
Оценка:
Здравствуйте, frogkiller, Вы писали:

К>>>template<template<class>class M, class A, class B, class C>
К>>>function<M<C>(*)(M<A>,M<B>)> liftM2(function<C(*)(A,B)> f)
К>>>{
К>>>    // \a -> (mb >>= \b -> f a b)
К>>>    function<M<C>(*)(A,M<B>)> f1 = bind(return_<M,C>, bind(pass<B,C>, _2, bind(f, _1 )));
К>>>    return bind(pass<A,C>, _1, bind(f1, _2));
К>>>}


К>>>int x = from_just( liftM2<Maybe,int,int>(operator+) (just<int>(1), just<int>(2)) );

К>>>Кажется, так.

F>Всё равно не понятно (наверное, я сильно тупой ), объясни, пожалуйста, :
F>1. Что такое pass?

Это я забыл сказать, pass — хаскельный оператор >>=. Надо же было его как-то назвать. Думал, догадаешься.

F>2. Вообще, правильно ли я понимаю работу bind:

F>Пусть f имеет тип function<C(*)(A,B)>.
F>Какой тип будет тогда у bind(f, _1) ? Или это расчёт на несуществующий карринг?

Опаньки! Чевой-то я там запутался.
Карринг нам потребуется — хотя и не повсеместно, но отчасти.

Я сейчас разберусь, как это грамотнее сделать на бусте, и напишу отдельно.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.