Здравствуйте, Ikemefula, Вы писали:

I>Возьми что нибудь посложнее, например парсер. Хочется иметь полный контроль типов, поддержку компилятора и задавать грамматику в виде максимально близком к БНФ.

Ну если посмотреть на код выдаваемый yacc+flex, то там монады довольно сложно найти))) Другое дело, что этот код и не предназначен для разглядывания...

Здравствуйте, Dair, Вы писали:

D>Для меня загадка — современные алгоритмы шифрования (криптографии). Мат.аппарата не хватает

D>На практическом уровне — public key/private key понятно, но чо там внутри — чисто магия.

Да ладно, если говорить о принципах, то там же всё вообще тривиально.

Вот смотри, предположим у нас есть функция y=exp(x); и соответственно обратная ей x=ln(y); Причём (и это ключевой момент) ln вычисляется намного дольше, чем exp. Кстати, это и для обычных exp и ln справедливо, а в асимметричной криптографии используется спец. вариант, в котором ln вычисляется годами... Теперь, при наличие пары таких функций, мы можем тривиально наладить защищённый канал.

Вот предположим у нас есть два человека (1 и 2) с каждый стороны и ещё третий, прослушивающий канал. 1 и 2 генерируют по одному случайному числу k1 и k2. Затем считают от них p1=exp(k1) и p2=exp(k2). И отсылают друг другу. В итоге у первого есть k1 и p2, у второго k2 и p1, а у прослушивающего p1 и p2. Теперь первые два считают число z=p2^k1=p1^k2=exp(k1*k2) — теперь у них есть некий общий секрет z, который они могут использовать например как ключ для обычного блочного шифрования данных и спокойно обмениваться ими. Ну а бедный подслушивающий будет занят вычислениями ln(p1) или ln(p2), для того чтобы получить тот же самый z...

А весь так называемый крутой мат. аппарат там как раз сводится к доказательствам, что все современные методы математики не умеют быстро посчитать ln... )))

Здравствуйте, alex_public, Вы писали:

_>Здравствуйте, gandjustas, Вы писали:

G>>Чем он симпатичный? Тем что все неявное скрыто от читающего? Тем что для проверки корректности кода нужно дополнительно вникать что будет если наступит конец файлы или число не может быть распарсено?
G>>Все эти неявные выходы усложняют анализ кода как человеком, так и компьютером. Если неявные эффектны делаем явными (выражаем в типах значений), то это упрощает анализ кода очень сильно. Проще анализ — меньше ошибок — выше скорость разработки.
G>>С другой стороны выражение всех эффектов усложняет написание кода, но тут и помогают монады.

_>Ну так в случае монад этот код всё равно остаётся скрытым, просто уже в самой монаде. Конечно если человек держит их все в уме, то код пишется/читается легко... Но он точно так же может держать в уме и сигнатуры используемого интерфейса api (с исключениями или без) и тогда код аналогично будет легко писаться/читаться.

Неверно. В монаде скрыт control flow для unhappy path, но не присутствие unhappy path. С исключениями скрывается именно присутствие неявных выходов, которые кроме как чтением документации не определить.

Здравствуйте, dimgel, Вы писали:

D>Здравствуйте, Greeter, Вы писали:

G>>Или не до конца понимаете в программировании?

D>Монады. Несколько раз подкатывал, без толку.
Истинно так. Тот еще монстр.

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

Вводная:
Linq операторы (Select, Where, Group, ...) -- это все монады (к этому я пришел читая какую-то статью типа "монады в картинках").
async/await из C# 5 -- это тоже монада (это я узнал от самого Эрика Майера (Erik Meijer) на курсе https://www.coursera.org/course/reactive)

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

Как я себе объясняю монады
Для себя, в голове, я представляю монаду как объект, который состоит из Объекта и Функции. Эта Функция может что-то сделать с Объектом по запросу пользователя, но пока не делает(такое вот обещание сделать что-то с объектом). Если вернуться к Linq, то Объект это таблица в базе, а функция, это, например, условие where salary > 5.
Когда пользователю нужны данные, то он может эти данные у монады получить. Тогда монада применяет Функцию к Объекту и возвращает результат (вот тут я точно наврал, но моя модель в голове без этого пункта не рабоает).

Круть заключается в том, что монады можно объединять, дополнять и выстраивать в цепочки.
Это все делается оператором, кот. в определении называется bind ((M t)->(t->M u)->(M u)). Суть его (опять же в моей голове) заключается вот в чем. Он говорит: представь, что результат монады уже посчитан, напиши функцию, которая что-то делает с этим результатом и передай мне. Я отдам тебе новую монаду, которая сделает то что должна была моя монада, плюс применит твою функцию к результату (тут все не полно, потому как не объясняет как из Users.Where().Select() получается один запрос, а не 2. Но у меня "простого" объяснения этому нет).

Вернемся к linq и async/await
Разбираем цепочку:
Users.Where(u=>u.Salary > 5).SelectMany(u=> Departments).OrderBy((u, d) => d.Name).Select((u, d)=> {u.Name, d.Name}).ToList()

Users =>
это монада состоящая из "таблицы в БД" (Объект) и "запроса" (функция) { UsersTable, "Select * from UsersTable"}
Users.Where(u=>u.Salary > 5) =>
произошла бинд магия, которая знает, что "Select *" и "where" можно объединить в один запрос => { UsersTable, "Select * from UsersTable u where u.Salary > 5"}
Users.Where(u=>u.Salary > 5).SelectMany(u=> Departments) =>
к объекту монады добавился еще один, а селект дополнился джоином => { {UsersTable, DepartmentsTable} , "Select * from UsersTable u join Departments d where u.Salary > 5"}
Вот тут моя абстракция потекла, потому как я понимаю, что в случае с обычным SQL нам нафик нужны две таблицы в Объекте и там может быть сразу вся база, но дело в том, что там у нас не sql, а список из ExpressionTree и нам нужны эти объекты, чтобы построить запрос.
Users.Where(u=>u.Salary > 5).SelectMany(u=> Departments).OrderBy((u, d) => d.Department) => { {UsersTable, DepartmentsTable} , "Select * from UsersTable u join Departments d where u.Salary > 5 order by d.Name"}
Users.Where(u=>u.Salary > 5).SelectMany(u=> Departments).OrderBy((u, d) => d.Name).Select((u, d)=> {u.Name, d.Name}) => ... идея понятна, надеюсь.


Как-то так, надеюсь хоть кто-то понял, что я только что написал Предлагаю ЭТО теперь обсудить.
А еще лучше перевести мой поток мыслей на нормальный человеческй язык.

СУВ, Aikin

Здравствуйте, gandjustas, Вы писали:

G>Неверно. В монаде скрыт control flow для unhappy path, но не присутствие unhappy path. С исключениями скрывается именно присутствие неявных выходов, которые кроме как чтением документации не определить.

Да, всё правильно, подходы у этих принципов абсолютно различные. Но ключевое преимущество (по сравнению с вариантом в лоб) у них общее — количество кода на обработку особой ситуации не зависит от количества операций в цепочке.

Ну а то, что придётся читать документацию для использования некого api — это вроде как абсолютно нормально. )))

Здравствуйте, Ikemefula, Вы писали:

I>Возьми что нибудь посложнее, например парсер. Хочется иметь полный контроль типов, поддержку компилятора и задавать грамматику в виде максимально близком к БНФ.

Я как-то делал ОО-аналог парсер-комбинаторов:
"реактивные":
http://thedeemon.livejournal.com/31050.html (Haxe)
и простые:
http://www.infognition.com/blog/2012/deciphering_grf_files.html (D)

Вместо всяких ">>" используется ".", код в целом пошумнее, но в общем выходит похоже на те парсер-комбинаторы, с которыми приходилось иметь дело на хаскеле и окамле.

Здравствуйте, Aikin, Вы писали:

A>Linq операторы (Select, Where, Group, ...) -- это все монады (к этому я пришел читая какую-то статью типа "монады в картинках").
A>async/await из C# 5 -- это тоже монада (это я узнал от самого Эрика Майера (Erik Meijer) на курсе https://www.coursera.org/course/reactive)

A>Это было из серии "зачем могут понадобиться монады в нормальных мультипарадигменных языках".

Это теоретически может служить аргументом, но только для тех, кто считает что в linq и async/await есть какой-то смысл...

A>Для себя, в голове, я представляю монаду как объект, который состоит из Объекта и Функции.

Ключевая ошибка. Причём там же прямо дальше по тексту есть практически правильный кусок "монада применяет Функцию к Объекту". Как она могла бы это делать, если и функция и объект — это её части? ) Сама на себя действует что ли? ))) Очевидно же даже прямо из этого текста, что объект и функция являются как бы параметрами монады, т.е. она является отдельной от них сущностью. Более того, монада — это чистая абстракция и не имеет прямого отображения на какие-то сущности языка. Ну разве что сопоставить ей саму строчку кода вида read>>parse>>write (ну или Linq выражение).

Собственно фраза "монада — это применение функции к объекту" — это и есть неплохое определение. ))) Только надо ещё уточнить, что применение особым образом и не произвольную функцию к произвольному объекту (иначе например банальная функция map была бы монадой), а вполне конкретных типов. А именно, речь идёт о функциях вида optional<R> F<T, R>(T). Optional — это естественно только для примера, а могут быть и совсем другие типы. Так вот монада умеет применить такую функцию F к объекту вида optional<T> (а не просто T!). И как раз благодаря этому и получается строить цепочки произвольной длины.

Здравствуйте, alex_public, Вы писали:

_>Собственно фраза "монада — это применение функции к объекту" — это и есть неплохое определение. )))
Ключевая проблема всех неплохих определений монады в том, что ими весь инет забит. Но все равно непонятно что это за зверь.

СУВ, Aikin

Здравствуйте, Aikin, Вы писали:

A>И даже больше, я могу попытаться объяснить их, на примерах. Может меня кто-то поправит и расскажет, что я нифига не понимаю. Тоже польза.
A>Linq операторы (Select, Where, Group, ...) -- это все монады (к этому я пришел читая какую-то статью типа "монады в картинках").
A>async/await из C# 5 -- это тоже монада (это я узнал от самого Эрика Майера (Erik Meijer) на курсе https://www.coursera.org/course/reactive)

Вот мой вариант "монады за две минуты".
Мысль 1. Всякий обычный императивный код

Делай то;
Делай сё

это на самом деле

r1 = Делай то;
r2 = Делай сё

где результаты r1 и r2 могут быть типа void.

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

r1 = Делай то;
r2 = function(x) { 
       Делай сё(x) } (r1)

Поскольку нам доступен результат не только предыдущей строчки, но и более ранних, то когда строчек много, получаются вложенные функции, замыкания.
Поэтому в обычном императивном коде символ ";" между предложениями это по сути волшебный оператор, у которого слева некоторое значение, а справа — функция, использующая это значение. Но если в языках вроде Си этот оператор жестко определен самым простым способом — передать значение в функцию, то в более интересных языках мы можем его переопределить и придумать ему более интересное содержание. Например, он может передавать значение в функцию не всегда, а только когда это не None. Это Maybe. Или он может получать значение-список, применять переданную функцию к каждому элементу, а полученные результаты склеивать в один список. Это List. Или может не передавать значение сразу, а запомнить функцию и переключиться на выполнение другой, а эту вызвать когда переданное слева значение "созреет". Это async. Или может переданную справа функцию заменить другой, обращающейся к базе. Это LINQ 2 SQL. Все волшебство происходит как следствие того, что мы монолитный код разбили на дерево из множества маленьких функций и позволили в явном виде этими кусочками оперировать как данными.

Всякое такое хитрое переопределение ";", простой передачи значения в функцию, назовем эффектом.

Мысль 3. Откуда берутся законы монады. Азы теорката: категория — это, грубо говоря, такой потенциально бесконечный ориентированный граф, узлы в нем называются объектами, а грани — стрелками, и в нем должны быть выполнены простые правила:
1) из всякой вершины есть стрелка в нее же, id : a -> a
2) если из А есть стрелка в Б, а из Б есть стрелка в В, то должна существовать стрелка из А в В, их композиция.
3) композиция id с любой стрелкой f (неважно в каком порядке) есть сама стрелка f.
Так вот, если в качестве объектов взять типы (Int, String, Bool...), а в качестве стрелок — функции (int_to_string, not, is_zero...), то получается как раз категория. Теперь, выше мы видели, что вместо простого применения функций мы можем захотеть хитрого применения — с эффектами. Возьмем и заменим все стрелки вида a -> b на стрелки с эффектами a -> m b. Чтобы у нас опять была категория, эти стрелки с эффектами должны подчиняться тем же трем законам категории. Осталось их аккуратно выписать, и получим законы монады для m.

Здравствуйте, Aikin, Вы писали:

A>Ключевая проблема всех неплохих определений монады в том, что ими весь инет забит. Но все равно непонятно что это за зверь.

Тут, имхо, окончательного понимания не будет, пока не освоишь исходное понятие из теории категорий.
http://thedeemon.livejournal.com/67392.html

Здравствуйте, alex_public, Вы писали:

_>Здравствуйте, gandjustas, Вы писали:

G>>Неверно. В монаде скрыт control flow для unhappy path, но не присутствие unhappy path. С исключениями скрывается именно присутствие неявных выходов, которые кроме как чтением документации не определить.

_>Да, всё правильно, подходы у этих принципов абсолютно различные. Но ключевое преимущество (по сравнению с вариантом в лоб) у них общее — количество кода на обработку особой ситуации не зависит от количества операций в цепочке.

Да, монады и сахар в языках для них для этого и были придуманы.


_>Ну а то, что придётся читать документацию для использования некого api — это вроде как абсолютно нормально. )))
Только это никто не делает. Поэтому явно выражать все в типах гораздо эффективнее, чем разбираться почему уже оно падает.

Здравствуйте, Aikin, Вы писали:

A>Ключевая проблема всех неплохих определений монады в том, что ими весь инет забит. Но все равно непонятно что это за зверь.

Хм, ну на мой взгляд даже в банальной википедии вполне понятная формулировка)

Здравствуйте, gandjustas, Вы писали:

G>Да, монады и сахар в языках для них для этого и были придуманы.

Ну так в итоге и получается, что в классических императивных языках уже заложено большая часть самых полезных монад. В виде конструкций языка, библиотечных функций и т.п. Соответственно не особо понятно зачем пытаться строить тоже самое, но только в максимально классическом "хаскелевском" виде и руками — теперь осознания что типа "я могу создавать монады"? )))

G>Только это никто не делает. Поэтому явно выражать все в типах гораздо эффективнее, чем разбираться почему уже оно падает.

Так это смотря в каком языке) Если говорить например про Жабку, то там вообще IDE автоматом определит что в каком-том месте кидаются исключения, сама вставит их импорт и код обработки. )))

Здравствуйте, alex_public, Вы писали:

I>>Возьми что нибудь посложнее, например парсер. Хочется иметь полный контроль типов, поддержку компилятора и задавать грамматику в виде максимально близком к БНФ.

_>Ну если посмотреть на код выдаваемый yacc+flex, то там монады довольно сложно найти))) Другое дело, что этот код и не предназначен для разглядывания...

При чем здесь yacc ?

Ты или не в теме или усиленно притворяешься Решай сам.

Здравствуйте, Ikemefula, Вы писали:

I>При чем здесь yacc ?

А ты предлагаешь писать парсер сложной грамматики (для простой то и boost.spirit сойдёт) руками и с нуля? )))

Здравствуйте, alex_public, Вы писали:

I>>При чем здесь yacc ?
_>А ты предлагаешь писать парсер сложной грамматики (для простой то и boost.spirit сойдёт) руками и с нуля? )))

Полагаю, выше речь шла о монадных парсер-комбинаторах — классическом применении монад (см. parsec и еще 197638 пакетов на hackage в разделе parsing). Но если парсер можно сделать на монадах, это не значит, что те же монады есть в любом другом парсере.

Здравствуйте, alex_public, Вы писали:

_>Ключевая ошибка. Причём там же прямо дальше по тексту есть практически правильный кусок "монада применяет Функцию к Объекту". Как она могла бы это делать, если и функция и объект — это её части? ) Сама на себя действует что ли? )))

— Весь этот разговор довольно примитивен. Мы ведь начали с того, кто я по своей природе. Если угодно, я полагаю себя... Ну скажем, монадой. В терминах Лейбница.
— А кто тогда тот, кто полагает себя этой монадой?
— Монада и полагает, — ответил я, твердо решив держать себя в руках.
(с) Пелевин, Чапаев и Пустота

Извините, Лейбницем навеяло.
P.S. Опечатка в цитате — моя.

Здравствуйте, D. Mon, Вы писали:

DM>Вот мой вариант "монады за две минуты".
<>
DM>Мысль 2. Каждую строчку можно считать функцией, принимающей результат вычисления предыдущей (может его использовать, может не использовать), и производящей какой-то свой результат. Т.е. код выше можно переписать как
<>

Это не "монады за 2 минуты", а "продолжения за 2 минуты".

DM>Мысль 3. Откуда берутся законы монады. Азы теорката: категория — это, грубо говоря, такой потенциально бесконечный ориентированный граф, узлы в нем называются объектами, а грани — стрелками, и в нем должны быть выполнены простые правила:
DM>1) из всякой вершины есть стрелка в нее же, id : a -> a
DM>2) если из А есть стрелка в Б, а из Б есть стрелка в В, то должна существовать стрелка из А в В, их композиция.
DM>3) композиция id с любой стрелкой f (неважно в каком порядке) есть сама стрелка f.
DM>Так вот, если в качестве объектов взять типы (Int, String, Bool...), а в качестве стрелок — функции (int_to_string, not, is_zero...), то получается как раз категория. Теперь, выше мы видели, что вместо простого применения функций мы можем захотеть хитрого применения — с эффектами. Возьмем и заменим все стрелки вида a -> b на стрелки с эффектами a -> m b. Чтобы у нас опять была категория, эти стрелки с эффектами должны подчиняться тем же трем законам категории. Осталось их аккуратно выписать, и получим законы монады для m.

Вот интересно, какой теоретический минимум необходим для объяснения монад на пальцах?

Теория множеств, поскольку Set — категория, хорошо иллюстрирующая и законы монад, и нотацию (do-нотация — это обобщение и развитие set comprehension)

Абстрактная алгебра, поскольку (>>=) это обобщение композиции функций (законы группы с нулём и единицей) — только вместо группы функций над однородным множеством (f,g : a->a, f.g : a->a) или над всеми типами (f : b->c, g : a->b, f.g : a->c) у нас двухслойное пространство (f : b->c', g : a->b', g>>=f : a->c') — соответственно, каждому b требуется привести в соответствие b'
Собственно, законы монад — это законы группы с единицей.
1) "в группе есть единица"
2) "группа замкнута"
3) "единица является нейтральным множителем как слева, так и справа"
4) ассоциативный закон, кстати!
Отсюда стремительно вытекает вопрос: а нет ли в этой группе нуля, который является идемпотентным множителем? (А он обычно есть — функция fail)
А если у нас есть 0 и 1, то нельзя ли сделать полукольцо со сложением? (А можно — класс MonadPlus)

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

Здравствуйте, alex_public, Вы писали:

I>>При чем здесь yacc ?

_>А ты предлагаешь писать парсер сложной грамматики (для простой то и boost.spirit сойдёт) руками и с нуля? )))

Ну то есть у тебя только два варианта — или yacc или спирит ? Я даже не знаю, что и сказать

Здравствуйте, alex_public, Вы писали:

I>>При чем здесь yacc ?

_>А ты предлагаешь писать парсер сложной грамматики (для простой то и boost.spirit сойдёт) руками и с нуля? )))

Давай внимательно посмотрим, чего твой спирит и yacc умеют

Покажи на yacc или спирит аналог вот такого кода

static void Main()
{
    var random = new Random();

    var values = Observable
        .Interval(TimeSpan.FromSeconds(1))
        .Select(_ => random.Next(1, 50));

    var ticks = values
        .Scan(StockTick.Empty, (acc, cur) => new StockTick(cur, cur - acc.Value))
        .Publish();

    var alerts = ticks.Parse(parser =>
        from next in parser
        let ups = next.Where(tick => tick.Change > 0)
        let downs = next.Where(tick => tick.Change < 0)
        let downAlert = from manyUps in ups.AtLeast(2).ToList()
                   from reversalDown in downs.NonGreedy()
                   where reversalDown.Change <= -11
                   select new StockAlert(manyUps, reversalDown)
        let upAlert = from manyDowns in downs.AtLeast(2).ToList()
                from reversalUp in ups.NonGreedy()
                where reversalUp.Change >= 21
                select new StockAlert(manyDowns, reversalUp)
        select downAlert.Or(upAlert).Ambiguous(untilCount: 1));

    using (ticks.Subscribe(WriteTick))
    using (alerts.Subscribe(WriteAlert))
    using (ticks.Connect())
    {
        Console.ReadKey();
    }
}