Что-то накопилось
материала про 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
Комментариев нет:
Отправить комментарий