Glasgow Haskell Compiler 9.4.1

Отсюда и получается, что все вычисления (и их эффекты) следуют строго друг за другом.

эффекты

Монады — достаточно плохой способ учета эффектов. А если в хаскеле ради учета эффектов нельзя ассоциативные монадические выражения вычислять не по порядку — так это вообще делает язык дефектным.

Чувак, даже я из твоей нотации ничего не понял. Но я всё ещё не понимаю, как ты собираешься параллелить код с монадами в общем случае. Потому что какое-нибудь IO например вообще нельзя трогать.

Это, похоже, чисто хаскелевская придумка, которая не имеет ничего общего с реальным положением дел.

А где-то написано что операция [монадического связывания] ассоциативна? Она там хитроассоциативна, согласно хаскелевской вики (https://wiki.haskell.org/All_About_Monads) закон «ассоциативности» выглядит так

(m >>= f) >>= g ==== m >>= (\x -> f x >>= g)

gns

А где-то написано что операция [монадического связывания] ассоциативна?

Связывания — нет. А вот оператор <=< и его развёрнутая версия и правда ассоциативны. Но параллельности от этого особо не получить.

Просто монады можно определить как через >>=, так и через <=<, и через join. В хацкелле просто так исторически сложилось, что выбрали bind. В теории, можно было бы любой из трёх.

Собственно, та фраза про моноид в категории эндофункторов, она как раз про <=<.

Но я всё ещё не понимаю, как ты собираешься параллелить код с монадами в общем случае.

Я не собираюсь параллелить код с монадами в *общем* случае. (За *эффективное* распараллеливание такого кода можно давать сразу 5-10 нобелевок. И я сомневаюсь, что это вообще можно сделать.)

Я привел пару *частных* случаев монад, когда они эффективно параллелятся, причем в значительной степени по причине определения монады, а не случайно. И сделал это чтобы оспорить утверждение Laz о том, что монады не параллелятся.

Чувак, даже я из твоей нотации ничего не понял.

Да, там очень лохмато и непривычно. Начнем с того, что я bind(x,y) иногда пишу как x.bind(y) — и считаю, что это удобнее, чем стрелки.

В хацкелле просто так исторически сложилось, что выбрали bind. В теории, можно было бы любой из трёх.

Кхм... а разве можно по-другому? bind покороче выглядит в исполняемом коде (а не в рассуждениях). Как бы выглядел хаскель (do-нотация или что-нить вместо нее), если бы там монады были основаны на двух других?

Потому что какое-нибудь IO например вообще нельзя трогать.

Когда я говорю о распараллеливании, то я называю монадой не то, что в хаскеле синтаксически укладывается в монаду, а именно то, что выполняет закон ассоциативности.

И тут у меня большие сомнения, что у IO он выполняется. Дело в том, что внешний мир не подчиняется нашей программе.

Т.е. у меня большие сомнения, что IO семантически — монада.

Да у тебя и самого по моему из рассуждений выходит что в общем случае ты ничего не сделаешь.

Я не подряжался на общий случай — только на частные. И этого уже достаточно.

Я привел пару *частных* случаев монад, когда они эффективно параллелятся, причем в значительной степени по причине определения монады, а не случайно. И сделал это чтобы оспорить утверждение Laz о том, что монады не параллелятся.

а, ок, не так понял, спасибо за пояснение, с такой т.з. согласен вполне.

спасибо за инфу.

Просто монады можно определить как через >>=, так и через <=<, и через join. В хацкелле просто так исторически сложилось, что выбрали bind. В теории, можно было бы любой из трёх.

Чисто гипотетически (потому что не полезу читать книжку), не должны поменяться свойства, просто иногда дожно быть более/менее удобно в определённых случаях.

Но и раз

Но параллельности от этого особо не получить.

то вероятно так оно и есть.

Раз уж меня упомянули в ответе на этот коммент, скажу.Если я правильно понял твою мысль, ты предлагаешь параллелить операции внутри монады. Из того, что данная конкретная последовательность операций параллелится в монаде по смыслу вычислений, не следует, что параллелить вообще можно (ибо синхронизация, барьеры, мьютексы и пр.). Это с практической точки зрения. С теоретической же, насколько я понял, параллельных веток тоже не предусматривается.

Смысл монады именно в последовательном вычислении. Поэтому вопрос оптимизации вычислений в монаде методом распараллеливания операций считаю досужей спекуляцией.

Т.е. у меня большие сомнения, что IO семантически — монада.

Не стоит сомневаться. https://stefan-klinger.de/files/monadGuide.pdf

Я привел пару частных случаев монад, когда они эффективно параллелятся, причем в значительной степени по причине определения монады, а не случайно.

Пример со сложением в Maybe настолько частный, что он даже совершенно не интересен. Давай добавим к сложению вычитание. Например:

s(x) = Just(x+1) если x+1 <= 1000, иначе Nothing
p(x) = Just(x-1) если x-1 >= 0, иначе Nothing

Теперь будь добр, распараллель по-монадически вот это вот:

Just(x).bind(s).bind(p)

Если там монада (а похоже на то), и Just(x).bindᵃ(p).bindᵇ(s).bindᶜ(p).bindᵈ(s). ... просто дают сужение интервала (к примеру до интервала a < x < 1000-d — но, естественно, не совсем такого) — то легко. Естественно, не твой короткий пример, а че-то подлиннее, типа Just(x).bindᵃ(p).bindᵇ(s).bindᶜ(p).bindᵈ(s)

Мне прям захотелось полноценный код выкатить (включая проверку монадичности), допустим на сишарпе. Тут можно проверить ассоциативность для конечного числа комбинаций, и затем отсюда будет следовать ассоциативность вообще (т.к. там степени).

-----

Just(x).bindᵃ(p) = Just(x).bind(p).bind(p). ... .bind(p).bind(p), где повторение сделано a раз

Как бы выглядел хаскель (do-нотация или что-нить вместо нее), если бы там монады были основаны на двух других?

Точно так же бы и выглядел. Bind реализовывается через любой из двух других операторов.

В принципе, идеальным вариантом было бы внести все три в класс Monad и реализовывать самый актуальный для конкретного типа.

Естественно, не твой короткий пример, а че-то подлиннее

Нет уж, давай для начала мой короткий пример рассмотрим, для x = 1000. Для начала средуцируем всё в лоб:

   Just(1000).bind(s).bind(p) = -- 1000+1 > 1000, поэтому s возвращает Nothing
 = Nothing.bind(p)            = 
 = Nothing

Так, теперь попробуем с «оптимизациями»:

   Just(1000).bind(s).bind(p) = -- 1000+1-1 = 1000, поэтому Just
 = Just(1000+1-1)             = 
 = Just(1000)

Вроде, правильно всё заоптимизировал, да? А чего ж тогда результаты не сходятся?

Потому что в твоем расчете у тебя bind не ассоциативный, и значит у тебя не монада. А меж тем похоже bind можно определить ассоциативно. И я сказал как (но там крайне желательно написать код, чтобы проверить, что я ничего не упустил).

И вот только после этого я буду параллелить :-) И моя работа будет тривиальна... ну почти :-)

Кстати, это будет хороший пример монады — если там все сойдется.

По аксиоматике монады должно быть ( Just(x).bind(s) ).bind(p) = Just(x).bind(f), где f(у) = s(у).bind(p)

Поэтому тебе надо определить bind() не только от p и s, но и от f. И вообще от всего, что вот так может получиться.

А без этого у тебя — не монада.

Потому что в твоем расчете у тебя bind не ассоциативный, и значит у тебя не монада.

Почему bind должен быть ассоциативным?

Потому, что математики определили монаду именно так. А если у тебя какая-то хрень типизирована как монада, но не ассоциативна (где надо) — то это не монада, хотя и может быть воткнута в хаскельный do syntax.

Кстати:

1. Вот https://wiki.haskell.org/Monad_laws

2. В случае с монадой, предложенной Laz можно *определить* bind(f) исходя из ассоциативности. И это вроде прокатит.

Потому, что математики определили монаду именно так.

Ага. Только там в определении <=<, который в хацкелле тоже есть. И вот он ассоциативен по самые гланды.

Со стрелками (в смысле, с бинарными операторами) удобно выглядят законы ассоциативности, но очень неудобно стрелки запоминать и различать. Слова так по-моему куда лучше.

Да похрен. У bind разные типы слева и справа. Я не понимаю, какую ассоциативность к этому ты хочешь прикрутить.

Потому что в твоем расчете у тебя bind не ассоциативный, и значит у тебя не монада.

Я во втором - «оптимизированном» - кейсе твои предыдущие выкладки воспроизвёл. Выходит, что в том твоём коде у тебя были не монады.

И я сказал как (но там крайне желательно написать код, чтобы проверить, что я ничего не упустил). И вот только после этого я буду параллелить :-) И моя работа будет тривиальна… ну почти :-)

Окэй, держи в курсе.

У bind разные типы слева и справа. Я не понимаю, какую ассоциативность к этому ты хочешь прикрутить.

Я объясню почему я считаю это ассоциативностью. Другие могут обосновывать по-другому, но в википедии это тоже называется «essentially associative».

Начну издалека. Есть, допустим, функция sin с типом R->R. Из нее можно сделать другую функцию, назовем ее sin' с типом (T->R)->(T->R) и определив sin'(f)(x)=sin(f(x)). В обычных случаях можно и обратно получить sin из sin' (хотя, подозреваю, что так не в любой категории).

Ты, конечно, вправе считать sin' другой функцией, но обычный студент-математик даже не задумывался о разнице между sin и sin'. Думаю, что даже не все аспиранты задумывались.

Теперь перейдем к bind. Аналогично введем f.bind'(g)(x)=f(x).bind(g) который по-сути совпадает с bind

Тогда получим (m.bind(f)).bind(g) = m.bind(f.bind'(g))

P.S. Более полный ответ видимо должен содержать обобщения монад.

Я во втором - «оптимизированном» - кейсе твои предыдущие выкладки воспроизвёл.

И как ты их воспроизвел?! Вот так что ли:

= -- 1000+1-1 = 1000, поэтому Just

В цитате точно не мои выкладки и не моя логика.

Мои выкладки, исходя из твоего определения, будут такими:

s(x) = Just(x+1) если x+1 <= 1000, иначе Nothing
p(x) = Just(x-1) если x-1 >= 0, иначе Nothing

Just(x).bind(s).bind(p) = unit(x).bind(s).bind(p) = s(x).bind(p) =
= (Just(x+1) если x+1 <= 1000, иначе Nothing).bind(p) =
= Just(x+1).bind(p) если x+1 <= 1000, иначе Nothing.bind(p) =
= unit(x+1).bind(p) если x+1 <= 1000, иначе Nothing =
= p(x+1) если x+1 <= 1000, иначе Nothing =
= (Just(x+1-1) если x+1-1 >= 0, иначе Nothing) если x+1 <= 1000, иначе Nothing =
= (Just(x) если x >= 0, иначе Nothing) если x <= 999, иначе Nothing =
= Just(x) если 0 <= x <= 999, иначе Nothing

Здесь тебе уже понятно, как можно параллелить выражения вида Just(x).bindᵃ(p).bindᵇ(s).bindᶜ(p).bindᵈ(s). ... ?

Теперь перейдем к bind. Аналогично введем f.bind’(g)(x)=f(x).bind(g) который по-сути совпадает с bind

Ну это <=< и есть.

ghci> :t (<=<)
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c
ghci> :t (=<<)
(=<<) :: Monad m => (a -> m b) -> m a -> m b

Видишь фишку?

Кстати, в моем предыдущем кейсе ∀x: Just(x).bind(F₅₅₅).bind(F₆₆₆) = Nothing. Я хотел это написать, но поленился сходить за индексами.

Так же и в твоем кейсе ∀x: Just(x).bind⁵⁵⁵(s).bind⁶⁶⁶(s) = Just(x).bind¹²²¹(s) = Nothing если х — натуральные (ты кстати вроде не сказал, какие у тебя х?).

А если целые или вещественные, то ∀x: Just(x).bind(p).bind⁵⁵⁵(s).bind⁶⁶⁶(s) = Nothing

А если целые или вещественные, то ∀x: Just(x).bind(p).bind⁵⁵⁵(s).bind⁶⁶⁶(s) = Nothing

Если числа вещественные, то ассоциативность отваливается, потому как сложение в IEEE754 этим свойством не обладает.

Можно взять вещественные неограниченной точности. У нас тут только +1 и -1, поэтому ассоциативность будет (для них, а не для IEEE754).

Тут можно на эту тему поспорить с целью уточнения формулировки, но это неинтересно.

Интересно то, что настоящие монады допускают распараллеливание в ряде важных частных случаев, а «монадосодержащий продукт в упаковке, выглядящей идентично натуральной» — как это сделано в хаскеле — не допускает.

При этом, возможно, в хаскеле можно добавить настояющую do-нотацию для настоящих монад, куда как-то запретить вход IO и подобным суррогатам. При этом по сигнатуре она может быть той же, что и обычная.

Про рыбку <=< вообще удобнее рассуждать, чем про bind. Но надо помнить, в какую она сторону. А мне такие вещи запоминать лень.

Про рыбку <=< вообще удобнее рассуждать, чем про bind. Но надо помнить, в какую она сторону. А мне такие вещи запоминать лень.

Можешь порассуждать про >=>. Она такая же, только в другую сторону. Выбирай любую!

При этом, возможно, в хаскеле можно добавить настояющую do-нотацию для настоящих монад, куда как-то запретить вход IO и подобным суррогатам. При этом по сигнатуре она может быть той же, что и обычная.

IO – это настоящая монада. Все законы соблюдены.

Ты за каким-то хером путаешь ассоциативность монадического связывания и операции с типом внутри. Это вообще никак не связанные вещи. Data.Proxy – это самая что ни на есть монада в любом смысле, какой не притяни, и все законы во всех операциях с Proxy соблюдаются. Но тем не менее, все твои выкладки ломаются на корню.

IO – это настоящая монада. Все законы соблюдены.

Кроме ассоциативности. Поэтому она и не параллелится (хотя если внешний мир делится на части, типа запросов к разным сайтам с независимой защитой от DDOS, то можно и ее параллелить — только вот как ты это объяснишь компилятору, что вот тут IO можно параллелить, а тут — нельзя?)

Ты за каким-то хером путаешь ассоциативность монадического связывания и операции с типом внутри.

Скорее, это не я, а ты и создатели хаскеля перепутали. Но я посмотрю, как ты обоснуешь свою точку зрения.

Напиши, допустим, на хаскеле чекер того, что ты считаешь ассоцитивностью монадического связывания (конечно же не в общем случае, а для небольшого набора конкретных значений переменных). Максимально просто.

Но тем не менее, все твои выкладки ломаются на корню.

Я не подряжался параллелить говно, которое не соблюдает ассоциативность. И не важно, как там в хаскеле оно называется — хоть монада.

Я не подряжался параллелить говно, которое не соблюдает ассоциативность.

В любой монаде в Haskell для оператора <=< соблюдается ассоциативность. Всё. Точка. Не очень понимаю, в чём именно твоё непонимание этого состоит.

Расскажи мне, каким образом в случае с Proxy ассоциативность ломается?

В любой монаде в Haskell для оператора <=< соблюдается ассоциативность. Всё. Точка.

Спасибо, поржал.

Ладно, смотри какой код я хочу увидеть от тебя (но на хаскеле):

auto xx = { ... };
auto yy = { ... };
auto zz = { ... };

for( auto x: xx ) for( auto y: yy ) for( auto z: zz ) 
{
  if( (x+y)+z != x+(y+z) )
  {
    std::cout << "ассоциативность нарушается при " << x << " " << y << " " << z << "\n";
    exit(); // вовсе не обязательно выходить, можно выставить флаг
  }
}
std::cout << "ассоциативность для набора проверена\n";

Этот код должен давать твое понимание «ассоциативность монадического связывания», но «не ассоциативность операции с типом внутри».

Либо предложи свой аналог подобного кода. Вовсе не обязательно выходить, можно выставить флаг. Можно запускать 2 инстанса программы в одинаковой внешней среде (причем запускать руками, а не из хаскеля). Или еще как-то.

Полиморфность по монадам не обязательно, главное чтобы было можно присобачить че-нить типа IO, State и в этом духе, а так же настоящие монады, меняя исходник в одном месте (а не прыгая по всему тексту).

Помощь зала при написании этого кода весьма приветствуется :-)

Ты хочешь какую-то хрень. Начиная с того, что далеко не для всех монад можно реализовать сравнение, и заканчивая тем, что так вообще нельзя ничего доказать.

«что проще на C# в функциональном стиле писать, чем использовать этот огрызок от окамла» - нагло врут даже не краснеют

За что купил, за то и продаю. Например, я что-то такое читал у известного штангиста-хаскеллиста thesz (thesz.livejournal.com).

Ты хочешь какую-то хрень... так вообще нельзя ничего доказать.

Дядя, а вы правда программист?

Если программист в чем-то уверен, то он не доказывает, а выставляет юнит-тесты и показывает, что они все проходятся.

«Хрень» это в первом приближении как раз юнит-тест (но во втором приближении там будут различия).

далеко не для всех монад можно реализовать сравнение

Да. Поэтому этот юнит-тест должен быть не в рамках программы, а путем сравнения нескольких выхлопов программы или даже выхлопов нескольких программ. Вот пример на c++, но должно быть на хаскеле. И еще тут пока что не монады!

#include <iostream>
#include <cstdlib>

int main(int argc, char** argv)
{
  if( argc!=2 ) { std::cout << "usage: assoc_test choice\nwhere choice is 1...6\n"; return 1; }
  int choice = atoi(argv[1]);

  auto x = 70;
  auto y = 80;
  auto z = 90;

  switch(choice)
  {
    case 1 : { auto L=x; auto R=y+z; auto result=L+R; std::cout << result << "\n"; return 0; }
    case 2 : { auto R=z; auto L=x+y; auto result=L+R; std::cout << result << "\n"; return 0; }
    case 3 : { auto R=y+z; auto L=x; auto result=L+R; std::cout << result << "\n"; return 0; }
    case 4 : { auto L=x+y; auto R=z; auto result=L+R; std::cout << result << "\n"; return 0; }
    case 5 : { auto result=x+(y+z);                   std::cout << result << "\n"; return 0; }
    case 6 : { auto result=(x+y)+z;                   std::cout << result << "\n"; return 0; }
    default: { std::cout << "incorrect input for choice: " << argv[1] << "\n";     return 2; }
  }
}

В переводе на хаскель варианты 1,2,3,4 видимо пишутся через do для IO, варианты 5 и 6 через обычный вызов. ЕМНИП в с++ до сих пор операнды + могут считаться в произвольном порядке.

Я считаю операцию + ассоциативной для чисел 70,80,90, если для всех 6 вариантов исполнения программа выдаст одинаковый результат. Я считаю операцию + ассоциативной для целых, если для всех целых x,y,z (не только констант, но и читаемых снаружи) все 6 вариантов исполнения программы выдадут одинаковый результат.

Подозреваю, что ты считаешь, что ДЛЯ РЫБОК (т.е. для <=< и >=>) варианты 2 и 3 не обязаны давать тот же результат, что и остальные. Тогда я не согласен твою ассоциативность называть ассоциативностью, а скажем «секвенциальной ассоциативностью» (а чтобы было совсем обидно — так «слабой ассоциативностью»).

Почему так? Потому что с ассоциативностью кое-что можно параллелить, а со слабой ассоциативностью — уже нельзя.

И подозреваю, что часть хаскельных монад держат ассоциативность, а часть — только слабую ассоциативность.

Кстати — а как по-твоему: для обычных ассоциативных операций (т.е. исключая операции <=< и >=> и bind) варианты 2 и 3 должны давать тот же результат в хаскеле, что и 1,4,5,6 ?

Окэй, держи в курсе.

Держу. Если по моему прошлому комменту Glasgow Haskell Compiler 9.4.1 (комментарий) все еще не ясно, как параллелить Just(x).bindᵃ(p).bindᵇ(s).bindᶜ(p).bindᵈ(s). ... , то уже на подходе программа на плюсах, которая будет это делать.

Ладно, ок. В хацкелле нет монад.

Но вообще, я всё ещё нифига не понимаю, что за ересь ты тут пишешь. И почему ассоциативность монадического связывания должна иметь что-то общее с подлежащим типом.

Распиши мне пожалуйста цепочку для Proxy. Это самый простой тип из вообще возможных.

Типичный хачкель тред:
1. Выяснять, что такое монада.
2. Срать наркоманским кодом друг в друга, иногда честно признаваясь, что ничего не понимают.
3. Почему хачкель непопулярен-то?!

Это херня в сравнении с тредами про C, где половина сишников не знает, что такое undefined behavior, и регулярно срет мимо буфера прямо как Stanson.

Что те, что другие одного поля ягоды 😄

лицензия хорошая(MIT), а не GPL.

Поделил на 0