Резюме: В статье приводятся примеры задач, для решения которых могут понадобиться монады.
Вместо вступления (перевод начался):
Во многих «введениях в монады» монады подаются как нечто сложно-объяснимое. Я же хочу показать, что это на самом деле, они не являются чем-то сложным. В действительности, сталкиваясь с различными проблемами в функциональном программировании вы будете непреклонно приходить к различным решениям, которые часто являются примерами монад. И я надеюсь, что вы научитесь изобретать их, если вы ещё не научились. Забегая вперёд скажу, что эти решения по сути являются одним и тем же решением. После прочтения вы наверное будете лучше понимать другие работы по монадам потому, что будете узнавать всё, что вы увидите как то, что вы уже сами изобрели.
Многие проблемы, которые пытаются решить монады связаны с проблемой «побочных эффектов». И мы начнём с них. (Замечу, что монады позволяют гораздо больше, чем возможность работать с побочными эффектами, в частности многие из объектов-контейнеров могут быть представлены как монады. Некоторые введения в монады не связывают эти 2 типа и концентрируются на одном или на другом типе.)
В императивных языках программирования таких как C++, функции ведут себя не так как функции в математическом понимании. Например, предположим, что функция C++ получает 1 аргумент — число с плавающей точкой и возвращает число с плавающей точкой.
Внешне это похоже на математическую функцию действующую из R в R, но функция C++ может сделать нечто большее, чем просто возвращение числа, которое зависит от аргументов. Она может читать и писать значения из глобальной памяти, а так же писать вывод на экран и получать входные данные от пользователя. В чистом функциональном языке, функции могут читать только то, что передаётся через аргументы и есть только единственный путь влияния на внешний мир — выдаваемое значение.
Итак, рассмотрим следующую проблему в чистом языке программирования: у нас есть функции f и g действующие R -> R, и мы хотим изменить эти функции так, чтобы они также выводили отладочную информацию. В Haskell f и g могут иметь следующие типы
Каким образом мы можем изменить типы f и g для того, чтобы допустить побочные эффекты? Ну на самом деле у нас нет выбора. Если мы хотим, чтобы f' и g' создавали строки и числа с плавающей точкой, тогда единственный возможный путь — это возвращение строки наряду с числами с плавающей точкой. Другими словами функции f' и g' должны иметь типы
Мы можем это изобразить на диаграмме
Будем называть их «отладочными функциями».
Предположим, что мы хотим отлаживать композицию двух таких функций. Мы можем записать простую композицию начальных функций, f и g, в форме f. g. Но для отладочных функций напрямую этого сделать нельзя. Поскольку нам бы хотелось, чтобы строки возвращаемые f' и g' объединялись в общую отладочную строку (одна из g' и за ней из f'). Но мы не можем напрямую объединить f' и g' потому, что тип возвращаемого значения g' не совпадает с типом аргументов f'. Мы можем записать код решения следующим образом:
Изобразим это на диаграмме
Каждый раз писать таким образом композицию двух функций сложно, и если мы захотим написать такое связывание везде в нашем коде, это будет сложной задачей. Что мы должны так это определить функцию высшего порядка для того, чтобы осуществить это связывание. Сложность заключается в том, что вывод g' не может быть подан на вход f' и нам надо «улучшить» f'. Для этого мы должны ввести функцию, назовём её bind, со следующими типами
Которая работает так, что
bind должна выполнять 2 задачи: она должна (1) применять f' к нужной части g' x и (2) объединять строку возвращаемую g' со строкой возвращаемой f'.
Упраженение 1
написать функцию bind.
Решение
Теперь мы можем писать композицию отладочных функций, f' и g'. Обозначим их композицию как f'°g'. Даже если несмотря на то, что вывод g' несовместим с входом f', у нас появился достаточно простой путь объединения этих операций. И это приводит к следующему вопросу: существованию «единичной» фунции. Обычно 1 (тождественное преобразование) имеет следующие свойства f × 1=f и 1 × f=f. Мы можем найти отладочную функцию (назовём unit) такую, что выполняется unit ° f = f ° unit = f. Очевидно, что мы можем написать функцию выводящую пустую отладочную информацию, а в остальном работающую как тождественное преобразование.
Упражнение 2
Введите unit.
Решение
Функция unit позволяет нам произвести «поднятие» функции в пространство отладочных. На самом деле:
или проще lift f = unit. f. «Поднятая» функция выполняет тоже, что и исходная и, что логично, выводит пустую строку как побочный эффект.
Упражнение 3
покажите, что lift f ° lift g = lift ( f. g )
Обобщая: функции bind и unit позволяют нам создавать отладочные функции напрямую и объединять обычные функции с отладочными естественным образом.
Верите или нет, но выполнив упражнения вы определили свою первую монаду. Сейчас возможно не очень понятно какая из структур является монадой или как могут выглядеть другие монады. Но вместо того, чтобы дать определение монады сейчас, я с помощью других более простых упражнений подведу к другим монадам таким образом, что вы сами поймете их общую структуру заслуживающую своего имени. Так же я уверен, что большинство людей столкнувшихся с поставленной проблемой, сами могут догадаться до функции bind для объединения отладочных функций. Так же я уверен, что вы могли уже придумать монаду, даже если вы не осознавали, что это была монада.
Рассмотрим функции sqrt и cbrt, которые вычисляют соответственно квадратный и кубический корень вещественного числа. Это функции действуют из Float в Float (так же sqrt должна выбрасывать исключение для отрицательных аргументов).
Сейчас создадим комплексные версии этих функций. Для каждого комплексного числа, кроме нуля, должно иметься 2 квадратных корня. Аналогично у каждого не-нулевого комплексного числа есть 3 кубических корня. Таким образом мы определим функции sqrt' и cbrt' так, чтобы они возвращали список чисел:
Мы будем называть их многозначными функциями.
Предположим, что мы хотим найти корень 6-ой степени из вещественного числа, в этом случае мы можем просто объединить квадратный корень и кубический корень. Другими словами мы можем определить корень 6-той степени как x = sqrt (cbrt x).
Рассмотрим функцию, которая возвращает все 6 корней 6-той степени комплексного числа используя sqrt' и cbrt'. Мы не можем просто записать объединение этих функций. Мы должны сначала вычислить кубические корни из числа, а затем квадратные корни из полученных значений и объединить все результаты один длинный список. Для этого мы должны написать функцию (назовём bind) с определением
Вот диаграмма, описывающая полный процесс. Мы хотим записать cbrt' один раз, но все ещё хотим применить sqrt' к полученным значениям.
Упражнение 4
Напишите реализацию bind.
Решение
Как мы можем записать единицу для многозначных функций? Единица возвращает 1 аргумент, таким образом, в многозначном варианте функции мы должны возвращать список состоящий из одного элемента. Назовём функцию unit.
Задача 5
Запишите unit.
Решение
И опять мы определим f ° g = bind f. g и поднятие lift f = unit. f. Поднятие делает то, что мы и предполагали — явным образом переводит обычную функцию в многозначную.
Упражнение 6
Покажите, что f ° unit = unit ° f = f и lift f ° lift g = lift (f.g)
И опять приведённая проблема непреклонно привела нас к функции bind.
После выполнения упражнений вы создали свою вторую монаду. Возможно вы уже понимаете общий шаблон разработки. Странно, что эти две различно выглядящие проблемы приводят к общим конструкциям.
Случайные числа в Haskell выглядят следующим образом
Идея состоит в том, что для того, чтобы сгенерировать случайное число нам необходимо зерно, и после генерации мы должны его обновить. В не-чистом языке мы можем сделать зерно глобальной переменной и пользователю не нужно работать с ней напрямую. Но в чистом языке зерно должно быть передано и получено явно (это так называемая подпись описывающая случайность). Замечу, что эта проблема похожа на вышеописанные отладочные случаи тем, что они возвращают дополнительную информацию используя пару. Но в данной проблеме мы к тому же ещё и передаём дополнительную информацию.
Итак, функция, которая является случайной функцией a -> b может быть переписана как функция a → StdGet → (b, StdGen), где StdGen это зерно.
Сейчас мы должны придумать, как сделать композицию 2-х случайных функций, f и g. «Настоящее» возвращаемое значение f должно быть передано в первый аргумент g. Тем временем и зерно, возвращаемое f вторым элементом пары, так же должно быть передано в g. Таким образом мы можем записать тип функции bind.
Упраждение 7
реализуйте bind
Решение
Теперь мы должны придумать единицу. Она должна иметь тип
и оставлять зерно не модифицированным.
Упражнение 8
Реализуйте unit.
Решение
или просто
И снова мы можем определить операции f ° g = bind f.g и поднятие lift f = unit. f. Поднятие делает то, что и предполагается — оно переводит обычную функцию в случайную (randomized) и оставляет зерно не изменённым.
Упражнение 9
Покажите, что f ° unit = unit ° f = f and lift f ° lift g = lift (f.g)
Теперь пришло время для того, чтобы вернуться к началу и заметить общую структуру.
Определим
Используем переменную m для того, чтобы реализовать Debuggable, Multivalued или Randomized. В каждом случае мы встречаемся с той же проблемой. Мы имеем функцию a -> m b, но мы должны уметь применять эту функцию к объектному типу m a вместо типа a. Для этого мы определяем функцию связывания (называемую bind) типа (a -> m b) -> (m a -> m b) и вводим тождественное преобразование unit :: a -> m a. В дополнение мы требуем, чтобы выполнялись требования: f ° unit = unit ° f = f и lift f ° lift g = lift (f.g), где (°) и lift, определены в терминах unit и bind.
Теперь, я могу сказать, что такое монада. Тройка объектов (m,unit,bind) — это монада, но для того, чтобы быть монадой они должны удовлетворять тем законам, которые вы доказывали выше. И я думаю, что в каждом из трёх случаев мы можете изобрести функцию bind, даже если вы не заметили что все 3 случая объединены общей структурой.
Итак, я должен связать это с определением монад Haskell. И первую вещь, которую я отразил и обозначил словом 'bind' — это определение функции bind, которая записывается как оператор >>=. Тогда связка f x переписывается как x >>=f. Во-вторых, unit называется return. И в третьих для переопределения функций >>= и return, мы должны использовать type classes. В Haskell'е Debuggable это монада Writer, Multivalued — монада List и Randomized это монада State. Если проверите определения следующих вещей
Control.Monad.Writer Control.Monad.List Control.Monad.State
вы увидете, с точностью до синтаксического сахара и это те определения, которые вы написали выше. Вот так вы были познакомились с монадами!
Я не хочу тратить на это много времени (и вы можете пропустить этот раздел), т.к. существует большое количество более хороших введений.
Вы уже видели, как функция bind может предоставлять удобный способ для связывания функций и избавляет от написания достаточно некрасивого кода. Но Haskell идёт дальше, и вам не надо даже напрямую использовать функцию bind, вы можете «попросить» Haskell вставить их автоматически.
Давайте вернёмся к изначальному примеру отладки, используя официальные type classes. Там, где мы использовали пару (a,s) мы будем использовать Writer (a,s) типа Writer Char. Для получения этой пары используем функцию runWriter. Предположим мы хотим добавить 1, умножить на 2 и отнять 7, и на каждом шаге записывать то, что мы делаем. Итого мы можем написать
Если мы применим функцию runWriter к этому результату мы получим (15,«inc.double.dec.»). Но код всё равно не красив. Чтобы улучшить его используем синтаксис do. Идея состоит в том, что
автоматически будет переписано компилятором в
Так же
будет переписано в
и
и оставляет просто выражением.
Мы можем переписать код следующим образом:
Данная запись весьма показательна. Когда мы записываем y <- ..., мы можем предположить, что выражение в правой части это просто x+1 с некими побочными эффектами вызываемыми операцией.
Другой пример. Напишем нашу функцию нахождения корня 6 степени в громоздкой форме
Мы можем переписать код в более читаемый
Мы можем написать код выглядящий, как обычный не многозначный код и неявно вызвать связывание bind, которое Haskell вставляет автоматически, делая её многозначной.
Создание такого синтаксиса это работа гения. Может быть вы бы смогли изобрести это, но я уверен, что я бы не смог. Но эти дополнения на самом деле лишь синтаксический сахар поверх монад. Я уверен, что вы бы смогли придумать нижележащее устройство монад.
Остаётся ещё одна вещь, на которую мы должны обратить внимание перед тем как вы будете полностью разбираться в монадах. Связь с внешним миром. Всё что написано выше может относиться к любому чистому функциональному языку. Но сейчас обратим внимание на ленивые чистые функциональные языки. В таких языках вы не имеете представление в каком порядке вещи будут вычисляться. Итак, если у Вас есть функция выводящая сообщение «Введите число» и другая функция запрашивающая число, вы не можете гарантировать, что сообщение будет написано до того, как число будет запрошено! Посмотрите на пример случайной функции, обратите внимание как случайное зерно ведётся через все функции так, чтобы оно могло использоваться при каждом вызове random. Происходит некое упорядочивание. Предположим у нас есть x >>= f >>= g Т.к. g использует зерно возвращаемое f мы можем быть уверены, что f сгенерирует число перед g. И это показывает, что в принципе монады могут быть использованы для упорядочивания вычислений.
Теперь предложим реализацию случайного числа в компиляторе. Это просто C или ассемблер код вставленный в выполняемый Haskell файл. Этот код изменяется для исполнения I/O мы можем гарантировать, что f выполняется перед g. Это в точности так как I/O работает в Haskell'е, мы выполняем все I/O в монаде. В этом случае функция, имеющая тип a->b и побочный эффект во внешнем мире, становится типа a -> IO b. Тип IO это черный ящик, мы не должны знать, что находится в нём. (Может быть он работает как пример random, может нет) Мы только должны знать, что в x>>=f>>=g f выполняется перед g.
И напоследок. Монады были изобретены в контексте теории категорий. И я оставлю эту связь на другой день.
И то, что мы собираемся сделать: мы хотим построить 2 (десятеричных) числа, выполнив следующие шаги
(1) создать случайное число в диапазоне [0,9]
(2) умножить его на 10
(3) прибавить другое случайное число из диапазона [0,9]
В общем случае это композиция чего-то такого addDigit. (*10). addDigit. Но мы знаем, что мы должны передавать случайное зерно через весь код. Сначала рассмотрим определение addDigit:
он возвращает пару состоящую из n+random чисел и новое зерно. Заметьте, что он использует зерно как дополнительный аргумент. Можно аргументировать, что функция может выглядеть addDigit n = let a = random in n + a `mod` 10 и она переносима в не-чистый язык.
Теперь введём операцию умножения на 10. Это обычная операция, которую мы можем «улучшить» используя поднятие. Получаем
И это решаюший момент. Мы не можем сделать композицию, а вместо этого мы можем использовать связывание для преобразование функций в тот формат, в котором они могут быть объединены. Итого addDigit. (*10) .addDigit превращается в
Сейчас мы создадим зерно используя мое любимое число и запустим код
Заметье, что при написании примеров я специально не использовал класс типов Monad. Поэтому от вас ничего не было спрятано и всё было сделано явно.
Вместо вступления (перевод начался):
Во многих «введениях в монады» монады подаются как нечто сложно-объяснимое. Я же хочу показать, что это на самом деле, они не являются чем-то сложным. В действительности, сталкиваясь с различными проблемами в функциональном программировании вы будете непреклонно приходить к различным решениям, которые часто являются примерами монад. И я надеюсь, что вы научитесь изобретать их, если вы ещё не научились. Забегая вперёд скажу, что эти решения по сути являются одним и тем же решением. После прочтения вы наверное будете лучше понимать другие работы по монадам потому, что будете узнавать всё, что вы увидите как то, что вы уже сами изобрели.
Многие проблемы, которые пытаются решить монады связаны с проблемой «побочных эффектов». И мы начнём с них. (Замечу, что монады позволяют гораздо больше, чем возможность работать с побочными эффектами, в частности многие из объектов-контейнеров могут быть представлены как монады. Некоторые введения в монады не связывают эти 2 типа и концентрируются на одном или на другом типе.)
Побочные эффекты: отладка чистых функций
В императивных языках программирования таких как C++, функции ведут себя не так как функции в математическом понимании. Например, предположим, что функция C++ получает 1 аргумент — число с плавающей точкой и возвращает число с плавающей точкой.
Внешне это похоже на математическую функцию действующую из R в R, но функция C++ может сделать нечто большее, чем просто возвращение числа, которое зависит от аргументов. Она может читать и писать значения из глобальной памяти, а так же писать вывод на экран и получать входные данные от пользователя. В чистом функциональном языке, функции могут читать только то, что передаётся через аргументы и есть только единственный путь влияния на внешний мир — выдаваемое значение.
Итак, рассмотрим следующую проблему в чистом языке программирования: у нас есть функции f и g действующие R -> R, и мы хотим изменить эти функции так, чтобы они также выводили отладочную информацию. В Haskell f и g могут иметь следующие типы
f,g :: Float -> FloatКаким образом мы можем изменить типы f и g для того, чтобы допустить побочные эффекты? Ну на самом деле у нас нет выбора. Если мы хотим, чтобы f' и g' создавали строки и числа с плавающей точкой, тогда единственный возможный путь — это возвращение строки наряду с числами с плавающей точкой. Другими словами функции f' и g' должны иметь типы
f',g' :: Float -> (Float,String)Мы можем это изобразить на диаграмме
x
|
+---+
| f' |
+---+
| \
| |
f x "f was called."
Будем называть их «отладочными функциями».
Предположим, что мы хотим отлаживать композицию двух таких функций. Мы можем записать простую композицию начальных функций, f и g, в форме f. g. Но для отладочных функций напрямую этого сделать нельзя. Поскольку нам бы хотелось, чтобы строки возвращаемые f' и g' объединялись в общую отладочную строку (одна из g' и за ней из f'). Но мы не можем напрямую объединить f' и g' потому, что тип возвращаемого значения g' не совпадает с типом аргументов f'. Мы можем записать код решения следующим образом:
let (y,s) = g' x
(z,t) = f' y in (z,s++t)
Изобразим это на диаграмме
x
|
+---+
| g' |
+---+
| \
+---+ | "g was called."
| f' | |
+---+ |
| \ |
| \ |
| +----+
| | ++ |
| +----+
| |
f (g x) "g was called.f was called."
Каждый раз писать таким образом композицию двух функций сложно, и если мы захотим написать такое связывание везде в нашем коде, это будет сложной задачей. Что мы должны так это определить функцию высшего порядка для того, чтобы осуществить это связывание. Сложность заключается в том, что вывод g' не может быть подан на вход f' и нам надо «улучшить» f'. Для этого мы должны ввести функцию, назовём её bind, со следующими типами
bind f' :: (Float,String) -> (Float,String)Которая работает так, что
bind :: (Float -> (Float,String)) -> ((Float,String) -> (Float,String))bind должна выполнять 2 задачи: она должна (1) применять f' к нужной части g' x и (2) объединять строку возвращаемую g' со строкой возвращаемой f'.
Упраженение 1
написать функцию bind.
Решение
bind f' (gx,gs) = let (fx,fs) = f' gx in (fx,gs++fs)Теперь мы можем писать композицию отладочных функций, f' и g'. Обозначим их композицию как f'°g'. Даже если несмотря на то, что вывод g' несовместим с входом f', у нас появился достаточно простой путь объединения этих операций. И это приводит к следующему вопросу: существованию «единичной» фунции. Обычно 1 (тождественное преобразование) имеет следующие свойства f × 1=f и 1 × f=f. Мы можем найти отладочную функцию (назовём unit) такую, что выполняется unit ° f = f ° unit = f. Очевидно, что мы можем написать функцию выводящую пустую отладочную информацию, а в остальном работающую как тождественное преобразование.
Упражнение 2
Введите unit.
Решение
unit x = (x,"")Функция unit позволяет нам произвести «поднятие» функции в пространство отладочных. На самом деле:
lift f x = (f x,"")или проще lift f = unit. f. «Поднятая» функция выполняет тоже, что и исходная и, что логично, выводит пустую строку как побочный эффект.
Упражнение 3
покажите, что lift f ° lift g = lift ( f. g )
Обобщая: функции bind и unit позволяют нам создавать отладочные функции напрямую и объединять обычные функции с отладочными естественным образом.
Верите или нет, но выполнив упражнения вы определили свою первую монаду. Сейчас возможно не очень понятно какая из структур является монадой или как могут выглядеть другие монады. Но вместо того, чтобы дать определение монады сейчас, я с помощью других более простых упражнений подведу к другим монадам таким образом, что вы сами поймете их общую структуру заслуживающую своего имени. Так же я уверен, что большинство людей столкнувшихся с поставленной проблемой, сами могут догадаться до функции bind для объединения отладочных функций. Так же я уверен, что вы могли уже придумать монаду, даже если вы не осознавали, что это была монада.
Контейнер: многозначные функции
Рассмотрим функции sqrt и cbrt, которые вычисляют соответственно квадратный и кубический корень вещественного числа. Это функции действуют из Float в Float (так же sqrt должна выбрасывать исключение для отрицательных аргументов).
Сейчас создадим комплексные версии этих функций. Для каждого комплексного числа, кроме нуля, должно иметься 2 квадратных корня. Аналогично у каждого не-нулевого комплексного числа есть 3 кубических корня. Таким образом мы определим функции sqrt' и cbrt' так, чтобы они возвращали список чисел:
sqrt',cbrt' :: Complex Float -> [Complex Float]Мы будем называть их многозначными функциями.
Предположим, что мы хотим найти корень 6-ой степени из вещественного числа, в этом случае мы можем просто объединить квадратный корень и кубический корень. Другими словами мы можем определить корень 6-той степени как x = sqrt (cbrt x).
Рассмотрим функцию, которая возвращает все 6 корней 6-той степени комплексного числа используя sqrt' и cbrt'. Мы не можем просто записать объединение этих функций. Мы должны сначала вычислить кубические корни из числа, а затем квадратные корни из полученных значений и объединить все результаты один длинный список. Для этого мы должны написать функцию (назовём bind) с определением
bind :: (Complex Double -> [Complex Double]) -> ([Complex Double] -> [Complex Double])Вот диаграмма, описывающая полный процесс. Мы хотим записать cbrt' один раз, но все ещё хотим применить sqrt' к полученным значениям.
64
|
+------+
+ sqrt'+
+------+
+8 / \ -8
+------+ +------+
| cbrt'| | cbrt'|
+------+ +------+
| | | | | |
2 . . -2 . .
Упражнение 4
Напишите реализацию bind.
Решение
bind f x = concat (map f x)Как мы можем записать единицу для многозначных функций? Единица возвращает 1 аргумент, таким образом, в многозначном варианте функции мы должны возвращать список состоящий из одного элемента. Назовём функцию unit.
Задача 5
Запишите unit.
Решение
unit x = [x]И опять мы определим f ° g = bind f. g и поднятие lift f = unit. f. Поднятие делает то, что мы и предполагали — явным образом переводит обычную функцию в многозначную.
Упражнение 6
Покажите, что f ° unit = unit ° f = f и lift f ° lift g = lift (f.g)
И опять приведённая проблема непреклонно привела нас к функции bind.
После выполнения упражнений вы создали свою вторую монаду. Возможно вы уже понимаете общий шаблон разработки. Странно, что эти две различно выглядящие проблемы приводят к общим конструкциям.
Более сложный пример побочного эффекта: случайные числа
Случайные числа в Haskell выглядят следующим образом
random :: StdGen → (a,StdGen)
Идея состоит в том, что для того, чтобы сгенерировать случайное число нам необходимо зерно, и после генерации мы должны его обновить. В не-чистом языке мы можем сделать зерно глобальной переменной и пользователю не нужно работать с ней напрямую. Но в чистом языке зерно должно быть передано и получено явно (это так называемая подпись описывающая случайность). Замечу, что эта проблема похожа на вышеописанные отладочные случаи тем, что они возвращают дополнительную информацию используя пару. Но в данной проблеме мы к тому же ещё и передаём дополнительную информацию.
Итак, функция, которая является случайной функцией a -> b может быть переписана как функция a → StdGet → (b, StdGen), где StdGen это зерно.
Сейчас мы должны придумать, как сделать композицию 2-х случайных функций, f и g. «Настоящее» возвращаемое значение f должно быть передано в первый аргумент g. Тем временем и зерно, возвращаемое f вторым элементом пары, так же должно быть передано в g. Таким образом мы можем записать тип функции bind.
bind :: (a → StdGen → (b,StdGen)) → (StdGen → (a,StdGen)) → (StdGen → (b,StdGen))
Упраждение 7
реализуйте bind
Решение
bind f x seed = let (x',seed') = x seed in f x' seed'
Теперь мы должны придумать единицу. Она должна иметь тип
unit :: a → (StdGen → (a,StdGen))
и оставлять зерно не модифицированным.
Упражнение 8
Реализуйте unit.
Решение
unit x g = (x,g)
или просто
unit = (,)
И снова мы можем определить операции f ° g = bind f.g и поднятие lift f = unit. f. Поднятие делает то, что и предполагается — оно переводит обычную функцию в случайную (randomized) и оставляет зерно не изменённым.
Упражнение 9
Покажите, что f ° unit = unit ° f = f and lift f ° lift g = lift (f.g)
Монады
Теперь пришло время для того, чтобы вернуться к началу и заметить общую структуру.
Определим
type Debuggable a = (a,String) type Multivalued a = [a] type Randomised a = StdGen -> (a,StdGen)
Используем переменную m для того, чтобы реализовать Debuggable, Multivalued или Randomized. В каждом случае мы встречаемся с той же проблемой. Мы имеем функцию a -> m b, но мы должны уметь применять эту функцию к объектному типу m a вместо типа a. Для этого мы определяем функцию связывания (называемую bind) типа (a -> m b) -> (m a -> m b) и вводим тождественное преобразование unit :: a -> m a. В дополнение мы требуем, чтобы выполнялись требования: f ° unit = unit ° f = f и lift f ° lift g = lift (f.g), где (°) и lift, определены в терминах unit и bind.
Теперь, я могу сказать, что такое монада. Тройка объектов (m,unit,bind) — это монада, но для того, чтобы быть монадой они должны удовлетворять тем законам, которые вы доказывали выше. И я думаю, что в каждом из трёх случаев мы можете изобрести функцию bind, даже если вы не заметили что все 3 случая объединены общей структурой.
Итак, я должен связать это с определением монад Haskell. И первую вещь, которую я отразил и обозначил словом 'bind' — это определение функции bind, которая записывается как оператор >>=. Тогда связка f x переписывается как x >>=f. Во-вторых, unit называется return. И в третьих для переопределения функций >>= и return, мы должны использовать type classes. В Haskell'е Debuggable это монада Writer, Multivalued — монада List и Randomized это монада State. Если проверите определения следующих вещей
Control.Monad.Writer Control.Monad.List Control.Monad.State
вы увидете, с точностью до синтаксического сахара и это те определения, которые вы написали выше. Вот так вы были познакомились с монадами!
Синтаксис монад
Я не хочу тратить на это много времени (и вы можете пропустить этот раздел), т.к. существует большое количество более хороших введений.
Вы уже видели, как функция bind может предоставлять удобный способ для связывания функций и избавляет от написания достаточно некрасивого кода. Но Haskell идёт дальше, и вам не надо даже напрямую использовать функцию bind, вы можете «попросить» Haskell вставить их автоматически.
Давайте вернёмся к изначальному примеру отладки, используя официальные type classes. Там, где мы использовали пару (a,s) мы будем использовать Writer (a,s) типа Writer Char. Для получения этой пары используем функцию runWriter. Предположим мы хотим добавить 1, умножить на 2 и отнять 7, и на каждом шаге записывать то, что мы делаем. Итого мы можем написать
return 7 >>= (\x -> Writer (x+1,"inc."))
>>= (\x -> Writer (2*x,"double."))
>>= (\x -> Writer (x-1,"dec."))
Если мы применим функцию runWriter к этому результату мы получим (15,«inc.double.dec.»). Но код всё равно не красив. Чтобы улучшить его используем синтаксис do. Идея состоит в том, что
do x <- y
more code
автоматически будет переписано компилятором в
y >>= (\x -> do
more code).
Так же
do
let x = y
more code
будет переписано в
(\x -> do
more code) y
и
do
expression
и оставляет просто выражением.
Мы можем переписать код следующим образом:
do
let x = 7
y <- Writer (x+1,"inc\n")
z <- Writer (2*y,"double\n")
Writer (z-1,"dec\n")
Данная запись весьма показательна. Когда мы записываем y <- ..., мы можем предположить, что выражение в правой части это просто x+1 с некими побочными эффектами вызываемыми операцией.
Другой пример. Напишем нашу функцию нахождения корня 6 степени в громоздкой форме
return 64 >>= (\x -> sqrt' x) >>= (\y -> cbrt' y)
Мы можем переписать код в более читаемый
do
let x = 64
y <- sqrt' x
z <- cbrt' y
return z
Мы можем написать код выглядящий, как обычный не многозначный код и неявно вызвать связывание bind, которое Haskell вставляет автоматически, делая её многозначной.
Создание такого синтаксиса это работа гения. Может быть вы бы смогли изобрести это, но я уверен, что я бы не смог. Но эти дополнения на самом деле лишь синтаксический сахар поверх монад. Я уверен, что вы бы смогли придумать нижележащее устройство монад.
Ввод/Вывод
Остаётся ещё одна вещь, на которую мы должны обратить внимание перед тем как вы будете полностью разбираться в монадах. Связь с внешним миром. Всё что написано выше может относиться к любому чистому функциональному языку. Но сейчас обратим внимание на ленивые чистые функциональные языки. В таких языках вы не имеете представление в каком порядке вещи будут вычисляться. Итак, если у Вас есть функция выводящая сообщение «Введите число» и другая функция запрашивающая число, вы не можете гарантировать, что сообщение будет написано до того, как число будет запрошено! Посмотрите на пример случайной функции, обратите внимание как случайное зерно ведётся через все функции так, чтобы оно могло использоваться при каждом вызове random. Происходит некое упорядочивание. Предположим у нас есть x >>= f >>= g Т.к. g использует зерно возвращаемое f мы можем быть уверены, что f сгенерирует число перед g. И это показывает, что в принципе монады могут быть использованы для упорядочивания вычислений.
Теперь предложим реализацию случайного числа в компиляторе. Это просто C или ассемблер код вставленный в выполняемый Haskell файл. Этот код изменяется для исполнения I/O мы можем гарантировать, что f выполняется перед g. Это в точности так как I/O работает в Haskell'е, мы выполняем все I/O в монаде. В этом случае функция, имеющая тип a->b и побочный эффект во внешнем мире, становится типа a -> IO b. Тип IO это черный ящик, мы не должны знать, что находится в нём. (Может быть он работает как пример random, может нет) Мы только должны знать, что в x>>=f>>=g f выполняется перед g.
Теория категорий
И напоследок. Монады были изобретены в контексте теории категорий. И я оставлю эту связь на другой день.
Дополнение: полный пример кода использующего случайные числа
import Random bind :: (a -> StdGen -> (b,StdGen)) -> (StdGen -> (a,StdGen)) -> (StdGen -> (b,StdGen)) bind f x seed = let (x',seed') = x seed in f x' seed' unit x g = (x,g) lift f = unit . f
И то, что мы собираемся сделать: мы хотим построить 2 (десятеричных) числа, выполнив следующие шаги
(1) создать случайное число в диапазоне [0,9]
(2) умножить его на 10
(3) прибавить другое случайное число из диапазона [0,9]
В общем случае это композиция чего-то такого addDigit. (*10). addDigit. Но мы знаем, что мы должны передавать случайное зерно через весь код. Сначала рассмотрим определение addDigit:
addDigit n g = let (a,g') = random g in (n + a `mod` 10,g')
он возвращает пару состоящую из n+random чисел и новое зерно. Заметьте, что он использует зерно как дополнительный аргумент. Можно аргументировать, что функция может выглядеть addDigit n = let a = random in n + a `mod` 10 и она переносима в не-чистый язык.
Теперь введём операцию умножения на 10. Это обычная операция, которую мы можем «улучшить» используя поднятие. Получаем
shift = lift (*10)
И это решаюший момент. Мы не можем сделать композицию, а вместо этого мы можем использовать связывание для преобразование функций в тот формат, в котором они могут быть объединены. Итого addDigit. (*10) .addDigit превращается в
test :: Integer -> StdGen -> (Integer,StdGen) test = bind addDigit . bind shift . addDigit
Сейчас мы создадим зерно используя мое любимое число и запустим код
g = mkStdGen 666 main = print $ test 0 g
Заметье, что при написании примеров я специально не использовал класс типов Monad. Поэтому от вас ничего не было спрятано и всё было сделано явно.