В статье в LinuxJournal приводится оригинальная интерпретация одной из концепций ФП — монад. Но все примеры были на языках, поддерживающих замыкания. В ожидании С++0х со встроенной их поддержкой попробовал переписать примеры "руками". Извиняюсь за обилие кода, меньше не получилось
Что мне не нравится:
1. Приходится постоянно выносить действительное имя класса в качестве шаблонного параметра, чтобы иметь возможность создавать объект нужного класса.
2. Чтобы связывать монады разных типов, приходится постоянно использовать dynamic_cast.
Профи буста, подскажите, пожалуйста, можно ли добиться аналогичного эффекта в статике? А главное, как это сделать...
PS. Про утечку памяти можно мне не объяснять, я и сам знаю, где она появляется, и как это лечится.
PPS. Подозреваю, что изобрёл велоспед, и если это так, не пинайте слишком сильно
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, frogkiller, Вы писали:
F>В статье в LinuxJournal приводится оригинальная интерпретация одной из концепций ФП — монад. Но все примеры были на языках, поддерживающих замыкания. В ожидании С++0х со встроенной их поддержкой попробовал переписать примеры "руками". Извиняюсь за обилие кода, меньше не получилось
Если уж тестировать свои руки, то не на Maybe, а сразу на List. У него более затейливые bind и join.
F>Что мне не нравится: F>1. Приходится постоянно выносить действительное имя класса в качестве шаблонного параметра, чтобы иметь возможность создавать объект нужного класса.
Ну и нормально, тип Maybe ведь параметризован типом элемента.
А вот класс Monad параметризуется шаблоном типа, — это challenge, как на С++ выразить наиболее общо.
Здравствуйте, Кодт, Вы писали:
К>Если уж тестировать свои руки, то не на Maybe, а сразу на List. У него более затейливые bind и join.
Не, чтобы тестировать руки на List'e, надо понимать, как там внутри что устроено. Я три раза переписал Maybe (предыдущий вариант ты видел в "Философии", он без RTI, но в нём не проходят связки с монадами разных типов), прежде чем начал хоть немного догадываться, как он работает. (Очень подозреваю, что проблема больше частью в области психологии и восприятия — то, что в ФП считается тривиальным, с одной стороны можно лего объяснить на пальцах, но с другой — при попытке сделать то же самое на императивном С++ с жёсткой типизацией — наступает ступор.)
Надеюсь, когда-нибудь руки дойдут и до более сложных конструкций.
F>>Что мне не нравится: F>>1. Приходится постоянно выносить действительное имя класса в качестве шаблонного параметра, чтобы иметь возможность создавать объект нужного класса.
К>Ну и нормально, тип Maybe ведь параметризован типом элемента. К>А вот класс Monad параметризуется шаблоном типа, — это challenge, как на С++ выразить наиболее общо.
Имхо это выглядит сильно корявым. Понятно, что здесь напрашивается аналогия с дотнетовскими метаданными, с помощью которых "лёгким движением руки" можно получить нужный тип, но хотелось как-нибудь этого избежать. Сначала я подумал, что может помочь виртуальный Clone(), но тогда придётся передавать указатель на объект во все методы, что по сути ничем не лучше выноса типа в параметр шаблона.
Другой, менее очевидный аспект:
Получается, что тип элемента, задаваемый TInstance, который потом протянется по цепочке шаблонов, определяется типом m2. А разве это то, что нам нужно? При таком подходе будет облом, если соединять монады, производные от IArithmetic и какого-нибудь IAnotherArithmetic, даже если они оба будут потомками одного класса, dynamic_cast от одного к другому вернёт 0.
Возможно, решение надо искать в виде:
и явно указывать тип элемента ->Add<CMaybeInt>(m2)...
Но это как минимум не красиво, и я не уверен в корректности работы такой конструкции.
Другой вариант — отказаться от RTI и шаманить с reinterpret_cast'ами, но это решение мне нравится ещё меньше, потому как накладывает сильные ограничения на получившуюся систему.
В общем понятно, что задача с наскока не решается, а дольше пяти минут над ней никто здесь думать не будет. А так, получается неплохое задание для какого-нибудь конкурса.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, 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>и явно указывать тип элемента ->Add<CMaybeInt>(m2)... F>Но это как минимум не красиво, и я не уверен в корректности работы такой конструкции.
F>Другой вариант — отказаться от RTI и шаманить с reinterpret_cast'ами, но это решение мне нравится ещё меньше, потому как накладывает сильные ограничения на получившуюся систему.
F>В общем понятно, что задача с наскока не решается, а дольше пяти минут над ней никто здесь думать не будет. А так, получается неплохое задание для какого-нибудь конкурса.
К чёрту реинтерпреты! Ты не с того конца начал: на питоне, с его рантайм-типизацией, была жалкая симуляция хаскельных монад.
Тут нужно использовать либо типизацию в compile time, либо (а скорее всего, вместе) то, как в хаскеле сделан рантайм и полиморфные методы.
Здравствуйте, Кодт, Вы писали:
К>Maybe как модель вычислений — это, практически, try-catch.
Это понятно, остальные в принципе тоже имеют не сильно сложную модель вычислений.
К>А вот как контейнер — как модель трансформации содержимого в монаду и обратно — вот это интересно.
Именно. А ещё интересно взаимодействие между монадами.
К>К чёрту реинтерпреты! Ты не с того конца начал: на питоне, с его рантайм-типизацией, была жалкая симуляция хаскельных монад.
Собственно у меня изначальный вопрос такой и был как обойтись статикой.
К>Тут нужно использовать либо типизацию в compile time, либо (а скорее всего, вместе) то, как в хаскеле сделан рантайм и полиморфные методы.
А как в хаскеле это сделано? Я читал про его полиморфизм, что называется, офигел мрачно, и отложил хаскель до лучших времён.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, 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;
}
Здравствуйте, Кодт, Вы писали:
К>Если уж тестировать свои руки, то не на 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.
Здравствуйте, 0xDEADBEEF, Вы писали:
DEA>...Что касается List, то имхо, он здорово похож на tuple, в особенности в свете недавних пропозалов добавить к нему операции slice и concat
Здравствуйте, Кодт, Вы писали:
К>Ну не скажи. К>Большинство случаев — это линейные вычисления, а 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 - фабричный метод для создания класса, по сути конструктор
// признаться, я плохо понимаю, что делает получившаяся конструкция
}
А вот это я совсем не понимаю (как и следующий 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>>
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, 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, которая вообще тащит функцию... Лучше тебе книжку по Хаскелю почитать
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)) );
Здравствуйте, Кодт, Вы писали:
К>Не всё так просто! К>Ленивость должна вычисляться единожды. К>Будет что-то этакое К>[...]
Угу, красиво.
К>Именно. К>Причём >>= оказалось можно выразить через более общий класс, 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), применяется вот так. И всё. А вот теории групп и тд. у меня не было.
Написал бы ты сам что ли на досуге
Курица — это инструмент, с помощью которого одно яйцо производит другие.
К>Эта процедура называется лифт — когда из обычной функции получается монадная.
Я всё-таки забыл сделать лифт результатов. Исправляюсь:
К>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)) );
Здравствуйте, 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".
К>>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
Курица — это инструмент, с помощью которого одно яйцо производит другие.
К>>>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) ? Или это расчёт на несуществующий карринг?
Опаньки! Чевой-то я там запутался.
Карринг нам потребуется — хотя и не повсеместно, но отчасти.
Я сейчас разберусь, как это грамотнее сделать на бусте, и напишу отдельно.
Перекуём баги на фичи!
Не, чтобы тестировать руки на List'e, надо понимать, как там внутри что устроено. Я три раза переписал Maybe (предыдущий вариант ты видел в "Философии", он без RTI, но в нём не проходят связки с монадами разных типов), прежде чем начал хоть немного догадываться, как он работает. (Очень подозреваю, что проблема больше частью в области психологии и восприятия — то, что в ФП считается тривиальным, с одной стороны можно лего объяснить на пальцах, но с другой — при попытке сделать то же самое на императивном С++ с жёсткой типизацией — наступает ступор.)
), объясни, пожалуйста, :