монады в сахаре

[thedeemon]

Недавно видел жалобу на то, что с монадами код разрастается, и простые выражения порой требуют несколько строчек для записи (речь про do-нотацию была). Сейчас осваиваю потихоньку язык Idris - это такой правильный хаскель с полноценными зависимыми типами (о которых чуть позже) и кучей встроенных плюшек для создания eDSL'ей (об этом вероятно еще позже). Так вот, в идрисе для монад сахара еще подсыпали, хочу поделиться. Пусть у нас есть функция readInt типа String -> IO Int, запрашивающая и получающая число откуда-то из внешнего мира, и мы хотим прочитать два числа и вывести их сумму. В языках вроде Clean или ML, где для монад вообще никаких спецсредств нету, это выглядит весьма печально. В хаскеле и идрисе есть привычная всем do-нотация:

main = do
  a <- readInt "a"
  b <- readInt "b"
  print (a+b)

Вот и получилось много строк на ровном месте. Первый кусочек сахара: monad comprehensions. Они когда-то были в хаскеле, потом потерялись, есть ли сейчас - не знаю. Идея в том, чтобы list comprehensions обобщить с монады List на произвольные монады:

main = [a + b | a <- readInt "a", b <- readInt "b"] >>= print

Не особо короче, чем вариант do с фигурными скобками и точками с запятой, но сама идея занятная.

Еще один вариант, доступный и в хаскеле: спрятать весь plumbing в операторы. Это как раз происходит, если вспомнить, что монада это функтор, а в наших языках еще и аппликативный:

class Functor f => Applicative (f : Type -> Type) where 
    pure  : a -> f a
    (<$>) : f (a -> b) -> f a -> f b
и
main = (pure (+) <$> readInt "a" <$> readInt "b") >>= print

(это на идрисе, в хаскеле некоторые значки будут другими, но в целом то же самое)

Второй кусочек сахара: idiom brackets. Специальный синтаксис для аппликативных функторов, где функции автоматически отображаются функтором с помощью pure, а их применения заменяются на применения образов через <$>:

main = [|readInt "a" + readInt "b"|] >>= print

(рассахаривается в предыдущий вариант)
В хаскеле похожая штука есть, но выглядит довольно страшно.

Еще пример для закрепления. Вот такую функцию

m_mul : Maybe Int -> Maybe Int -> Maybe Int
m_mul (Just x) (Just y) = Just (x * y)
m_mul _ _ = Nothing

можно записать как

m_mul x y = [| x * y |]

Comments

[109.livejournal.com]

та шо цэ такэ, монада?

[metaclass.livejournal.com]

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

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

[gds.livejournal.com]

ха-хаа, монада это не typeclass. Разве что тайпклассы используют для изображения монад в некоторых недоязычках, но это же мелочи.

[thedeemon.livejournal.com]

Функтор и пара естественных преобразований, удовлетворяющие кое-каким условиям.

Вообще, это знание - prerequisite для моих читателей, тема раскрыта множество раз elsewhere. Сейчас вон даже Александреску, выступая с лекциями в Фейсбуке, говорит, что хаскель всякий знает или должен знать.

[109.livejournal.com]

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

[thedeemon.livejournal.com]

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

[109.livejournal.com]

ну нашёл что-то, читаю. пока получается, что монада - это generic class, параметризованный двумя типами. большей специфики пока обнаружить не удаётся, поскольку приводятся примеры монад, между которыми мало общего, кроме двух type parameters.

[thesz.livejournal.com]

Это класс параметризованных классов, если считать тип и класс эквивалентными. m - это класс классов или конструктор типов, поскольку чтобы стать типом, его ещё надо чем-то параметризовать (отсюда и m a).

Поэтому m может быть и списком, и функций. И можно написать код, которому пофиг на внутреннее представление.

[109.livejournal.com]

> Это класс параметризованных классов, если считать тип и класс эквивалентными.

okay, okay. класс generic классов, параметризованных двумя типами. так нормально?

и нет, я не готов считать тип и класс эквивалентными. меня учили, что тип может быть классом, а может и не быть (struct, например).

[thedeemon.livejournal.com]

Если заходить со стороны кода, то это конструктор типов (функтор) с определенным интерфейсом для композиции. Из стандартной библиотеки Идриса:

class Functor (f : Type -> Type) where 
    fmap : (a -> b) -> f a -> f b

class Functor f => Applicative (f : Type -> Type) where 
    pure  : a -> f a
    (<$>) : f (a -> b) -> f a -> f b

class Applicative m => Monad (m : Type -> Type) where 
    return : a -> m a
    (>>=)  : m a -> (a -> m b) -> m b

flatten : Monad m => m (m a) -> m a
flatten a = a >>= id

Классические примеры подходящих конструкторов: List, Maybe, IO. Это все функторы, для которых можно описать соответствующие реализации упомянутых выше требуемых тайпклассом методов. В случае IO это оказывается хороший способ обеспечить нужный порядок выполнения эффектов вне зависимости от ленивости/строгости языка.

[109.livejournal.com]

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

все упомянутые примеры (List, Maybe, IO) в терминах сишарпа - это generic classes, параметризованные двумя типами. ещё какая-нибудь специфика есть, или это всё?

[thedeemon.livejournal.com]

Я помню, элементы теорката мы с вами обсуждали, понятие функтора оттуда должно быть вам знакомо. Обсуждаемое действительно очень похоже на generic class, если вычесть ту дополнительную смысловую нагрузку, которую ОО языки вроде C# навешивают на слово class. Generic type, если угодно, тип, параметризованный типом. Так вот, если для такого параметризованного типа реализовать упомянутые выше методы, и если поведение их будет соответствовать монадным законам, то такой генерик-тип - монада. Законы:
(return x) >>= f ≡ f x
m >>= return ≡ m
(m >>= f) >>= g ≡ m >>= ( \x -> (f x >>= g) )

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

[sassa-nf.livejournal.com]

Ну что делать, если у концепции прямого аналога нет.

Генерик класс в смысле ООП - это совсем не функтор. Они хоть и отображают "классы", но недостаёт способа отображать методы.

Вот если бы был фантастический ООП язык, в котором у "класса" List[Int] появлялись методы increment, +, * и константа 0, волшебным образом позаимствованные у Int и доопределённые для списка; а у "класса" List[String] появлялись методы append, charAt, ... и константа "пустая строка"; и у класса List[List[Int]] появлялись методы increment, +, *, ........ позаимствованные у List[Int] и доопределённые до List[List[Int]] и т.д., рекурсивно, вот ТОГДА это был бы функтор - то есть, когда этот генерик класс не только умеет строить списки определённого типа, но и дополняет список методов, заимствуя методы у параметра.

Это не означает, что функтор вот такой вот и есть; это лишь эскиз, как он мог бы более-менее похоже выглядеть в ОО языке. Понять функтор с точки зрения не функционального языка трудно по той причине, что даже в описанном выше виде List[Int] отображает только методы собственно Int, а не все-все функции, которые принимают Int как аргумент. По той же причине и "польза" в ОО языке была бы микроскопической - ну или по-крайней мере она не масштабируется с количеством написанных программ.


В ОО языках прямого аналога этому нет; да даже и кривого аналога "автодополнения" методов нет. В известных мне ОО языках даже List[Int] не является классом отдельным от List[String], поэтому в кавычках. С этим ничего нельзя поделать; нужно как-то въезжать, больше ничего не остаётся.

[109.livejournal.com]

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

[thedeemon.livejournal.com]

Достаточно же fmap определить, чтобы все эти функции над интами отображать в функции над списками.

[sassa-nf.livejournal.com]

да, но как ООписту объяснить, что за fmap и где он в сишарпе :)

[thedeemon.livejournal.com]

генерик метод описать

[sassa-nf.livejournal.com]

ну если в сишарпе можно метод в метод передавать, то ок

[juan-gandhi.livejournal.com]

Не хочешь мой тьюториал почитать?
Вообще, монадных тьюториалов уже сотни, наверное.

[109.livejournal.com]

я пытался, ни фига не понятно. собственно, ты же и не ставишь целью, чтобы [другим] понятно было, так тут no surprise.

[juan-gandhi.livejournal.com]

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

[109.livejournal.com]

come on, Вова. зачем этот самообман? :)

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

[juan-gandhi.livejournal.com]

Очень, очень любопытно.
Мы оба, собственно, пришли к выводу, что разговаривать нам не о чём.

[migmit.livejournal.com]

Ну, в смысле "что такое" вам тут уже понаписали.

А в смысле "как работает" - вот мой вариант:

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


for a in [1..100]:
for b in [a..10]:
for c in [1..a+b]:
...ешё много for-ов


или:


a = do_something_1(&success);
if (success) {
b = do_something_2(a, &success);
if (success) {
c = do_something_3(a, b, &success);
...
}
}


Можно и ещё примеров подобрать, но суть в этом.

Правильно подобранная монада делает из этого вот что:


a <- [1..100]
b <- [a..100]
c <- [1..a+b]
...


и, соответственно,


a <- do_something_1()
b <- do_something_2(a)
c <- do_something_3(a, b)
...


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

[109.livejournal.com]

в вашем описании это ещё хуже, чем перегрузка операторов :)

отличный способ выстрелить себе в ногу, и мало что кроме этого.

но я не думаю, что цель монад - спрятать от читателя control flow.

[migmit.livejournal.com]

Во-первых, чем вам не нравится перегрузка операторов? Во всяком случае, чем она хуже перегрузки функций?

Во-вторых, не спрятать, а обобщить.

В-третьих, если есть явный паттерн, то оформить его в отдельную сущность - правильный подход.