Записки программиста, обо всем и ни о чем. Но, наверное, больше профессионального.

2014-10-08

Monads without mistery (or misery)

Что-то накопилось материала про FP (functional programming).

Как считает весьма авторитетный дядя (Brian Beckman), пришло время, когда кардинальный разрыв между двумя принципиально разными подходами к программированию (от железа к математике версус от математики к железу) сходит на нет. Ключевой точкой в этом процессе устранения разрыва он считает появление языка F#. Подробнее об этом вы услышите в конце ролика http://youtu.be/ZhuHCtR3xq8
Это видео лекции, зачитанной Брайаном, с целью разъяснить косным императивным программерам, что такое монады. Я это видео нашел на странице
где сделана попытка популяризации функционального подхода в веб программировании.

Зачем нам может понадобится функциональное программирование? Чтобы дать нам возможность строить все более и более комплексные системы.

Другие материалы:

Четыре часа видео со встречи русскоязычных функциональщиков:
на странице есть очень интересные комментарии, почитайте, не пожалеете.

О Haskell по-человечески — книга


Возвращаясь к монадам. Что же рассказал нам Брайан Бэкман?
Brian Beckman (http://youtu.be/ZhuHCtR3xq8) monads without mistery (or misery)
Мой очень краткий конспект.

Strictly speaking you have to know category theory, но для того, чтобы использовать Haskell и монады на практике, теорию категорий можно отложить.

В функциональном программировании мы обращаемся с функциями так же как и с данными, без разницы, что функция, что дата. Это можно даже доказать: любая функция может быть заменена выборкой из таблицы (table lookup), на входе параметр, делаем поиск по таблице, на выходе дата. Это часто делается для ускорения вычислений — вычисления проводятся заранее. В итоге, формально, любая функция может быть выражена через универсальный код поиска в таблице, это будет операция. Все остальное — дата. Оказывается, что все функции выражаются через данные.

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

Обьяснение монад в 4 шага: функции, моноиды, снова функции, монады.

Функции.
Вместо «int x;» будем писать «x: int», что означает «x is a member of the set of int», «x E int».
Типы и сеты — почти одно и то же.
Функция будет записана как «f: int -> int» (берет инт и возвращает инт).
Запишем, что x это любой тип a: «x: a», функция «f: a -> a» берет а и возвращает а.
И еще одна функция «g: a -> a».

Теперь как комбинировать функции.
Например, комбинировать можно так: «f(g(a))» или так: «g(f(a))», что означает фактически вызов одной функции с передачей ей в качестве параметра результата другой функции.
Термин «function application» идентичен «calling a function».
Перепишем «f(g(a))» без скобочек: «f(g a)».
На самом деле скобочки нужны из-за curry, ибо если записать «f h g» то это будет эквивалентно «(f h) g».
Добавим нотацию: функция «(f о g) a» это есть «f(g a)» где «о» это little circle.
Тогда «h = (f o g)»; тип новой функции h: «h: a -> a».

Моноиды.
Взяли две функции и соорудили третью, того же типа, это основа моноид, позволяет создавать сложность из простоты.
Есть пачка строительных блоков — функций, есть правило - little circle, для комбинирования этих блоков произвольным образом. Получаем способ построения сложного из простых блоков.
Простых в смысле — маленьких.

little circle это композиция (composition), правило композиции.
Типы должны быть совместимы, базовый оператор композиции должен реализовывать правила композиции.

Моноид - набор (set/collection) чего-то (в нашем примере - функций) плюс правила композиции/комбинирования этих чего-то. Правила подчиняется неким метаправилам.

В любом моноиде должно работать правило ассоциативности:
«x combine (y combine z) = (x combine y) combine z»
Моноид должен содержать специальный member (unit) такой, что
«x combine unit = x; unit combine x = x».
Коммутативность — метаправило, которое моноиду соблюдать не обязательно: запросто может быть
«x combine y != y combine x»

Обратно к функциям.
Докажем, что наши функции ассоциативны:
«(f o g) o h = f o (g o h) = f(g(h a))»
Определим special member или unit как «id: a -> a» такой, что «id a = a»
тогда «f o id = f» и наоборот.

Переходим к монадам.
Пусть наши функции теперь будут возвращать некий трансформ от «а».
«a: f: a -> Ma»
M может быть чем угодно и делать что угодно, но оно одно для всех. Сайдэффекты в нем и содержатся, если они есть.

Compositionality is the way to control complexity.
Мы берем сайдэффекты под контроль, заворачивая их в монады, которые суть продвинутые моноиды. После чего мы можем делать любые композиции из функций, не опасаясь выстрелить себе в ногу (или голову). Как это сделать?

Входит лямбда.
Если вы не знаете, что такое лямбда в языках программирования, то можно сказать, это анонимная функция или функциональное выражение.
Лямбду запишем так: «\a -> (f a)». То есть на входе «а» и на выходе «Ма».
Мы уже знаем, что тип этой лямбды = Ma.
Теперь изобретем (программер должен его реализовать и это самое сложное) оператор «bind» (or «shove») записываемый как «>>=» это композиционный оператор для монад, подчиняющийся метаправилам.
Этот оператор каким-то образом пихает полученный «Ma» в другую лямбду, к примеру «\a -> (g a)».
Получается, с помощью этого оператора мы скомбинировали две «Ma»;
композиция превращает «a» в «Ma»:
«\a -> [(f a) >>= \a -> (g a)]»
для достижения симметрии.
Причем левую лямбду «\a» можно опустить для краткости.

Смысл оператора shove (bind) в том, чтобы иметь возможность получать на вход «Ma».
Вывод — функции живут в моноидах, дата (сайд эффекты) «Ma» живет в монадах.
Таким хитрым переподвывертом мы сохраняем возможность композиции и, следовательно, контроль над сложностью не взирая на то, что воткнули в систему сайдэффекты.
Остался «unit», его тоже надо задизайнить «return: a -> Ma» чтобы он не портил систему.
В качестве упражнения предлагается сделать монаду пустую, которая ничего не делает, только тип меняет (с числа на строку?).

Входит F#
Как здорово, что у нас теперь есть F#




original post http://vasnake.blogspot.com/2014/10/monads-without-mistery-or-misery.html

Комментариев нет:

Отправить комментарий

Архив блога

Ярлыки

linux (241) python (191) citation (185) web-develop (170) gov.ru (156) video (123) бытовуха (111) sysadm (100) GIS (97) Zope(Plone) (88) Book (81) programming (81) бурчалки (80) грабли (77) development (73) Fun (72) windsurfing (72) Microsoft (64) hiload (62) opensource (58) internet provider (57) security (57) опыт (55) movie (52) Wisdom (51) ML (47) language (45) hardware (44) JS (41) curse (40) money (40) driving (39) DBMS (38) bigdata (38) ArcGIS (34) history (31) PDA (30) howto (30) holyday (29) Google (27) Oracle (27) virtbox (27) health (26) vacation (24) AI (23) Autodesk (23) SQL (23) Java (22) humor (22) knowledge (22) translate (20) CSS (19) cheatsheet (19) hack (19) tourism (18) Apache (16) Manager (15) web-browser (15) Никонов (15) happiness (14) music (14) todo (14) PHP (13) weapon (13) HTTP. Apache (12) SSH (12) course (12) frameworks (12) functional programming (12) hero (12) im (12) settings (12) HTML (11) SciTE (11) crypto (11) game (11) map (11) scala (10) HTTPD (9) ODF (9) купи/продай (9) benchmark (8) documentation (8) 3D (7) CS (7) DNS (7) NoSQL (7) Photo (7) cloud (7) django (7) gun (7) matroska (7) telephony (7) Microsoft Office (6) VCS (6) bluetooth (6) pidgin (6) proxy (6) Donald Knuth (5) ETL (5) NVIDIA (5) REST (5) bash (5) flash (5) keyboard (5) price (5) samba (5) CGI (4) LISP (4) RoR (4) cache (4) display (4) holywar (4) nginx (4) pistol (4) xml (4) Лебедев (4) IDE (3) IE8 (3) J2EE (3) NTFS (3) RDP (3) USA (3) mount (3) spark (3) Гоблин (3) кухня (3) урюк (3) AMQP (2) ERP (2) IE7 (2) NAS (2) Naudoc (2) PDF (2) address (2) air (2) british (2) coffee (2) font (2) ftp (2) holiday (2) messaging (2) notify (2) sharepoint (2) ssl/tls (2) stardict (2) tests (2) tunnel (2) udev (2) APT (1) CRUD (1) Canyonlands (1) Cyprus (1) DVDShrink (1) Jabber (1) K9Copy (1) Matlab (1) Palanga (1) Portugal (1) VBA (1) WD My Book (1) autoit (1) bike (1) cannabis (1) chat (1) concurrent (1) dbf (1) ext4 (1) idioten (1) krusader (1) license (1) mindmap (1) pneumatic weapon (1) quiz (1) regexp (1) robot (1) science (1) serialization (1) tie (1) vim (1) Науру (1) крысы (1) налоги (1) пианино (1)

Google+ Followers