Миран Липовача - Изучай Haskell во имя добра!

ghci> let f = (+1) . (*100)

ghci> f 4

401

ghci> let g = (x –> return (x+1)) <=< (x –> return (x*100))

ghci> Just 4 >>= g

Just 401

В данном примере мы сначала произвели композицию двух обычных функций, применили результирующую функцию к 4, а затем произвели композицию двух монадических функций и передали результирующей функции Just 4 с использованием операции >>=.

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

ghci> letf = foldr (.) id [(+1),(*100),(+1)]

ghci> f 1

201

Функция f принимает число, а затем прибавляет к нему 1, умножает результат на 100 и прибавляет к этому 1.

Мы можем компоновать монадические функции так же, но вместо обычной композиции используем операцию <=<, а вместо id – функцию return. Нам не требуется использовать функцию foldM вместо foldr или что-то вроде того, потому что функция <=< гарантирует, что композиция будет происходить монадически.

Когда вы знакомились со списковой монадой в главе 13, мы использовали её, чтобы выяснить, может ли конь пройти из одной позиции на шахматной доске на другую ровно в три хода. Мы создали функцию под названием moveKnight, которая берёт позицию коня на доске и возвращает все ходы, которые он может сделать в дальнейшем. Затем, чтобы произвести все возможные позиции, в которых он может оказаться после выполнения трёх ходов, мы создали следующую функцию:

in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight

И чтобы проверить, может ли конь пройти от start до end в три хода, мы сделали следующее:

canReachIn3 :: KnightPos –> KnightPos –> Bool

canReachIn3 start end = end `elem` in3 start

Используя композицию монадических функций, можно создать функцию вроде in3, только вместо произведения всех позиций, которые может занимать конь после совершения трёх ходов, мы сможем сделать это для произвольного количества ходов. Если вы посмотрите на in3, то увидите, что мы использовали нашу функцию moveKnight трижды, причём каждый раз применяли операцию >>=, чтобы передать ей все возможные предшествующие позиции. А теперь давайте сделаем её более общей. Вот так:

import Data.List

inMany :: Int –> KnightPos –> [KnightPos]

inMany x start = return start >>= foldr (<=<) return (replicate x moveKnight)

Во-первых, мы используем функцию replicate, чтобы создать список, который содержит x копий функции moveKnight. Затем мы монадически компонуем все эти функции в одну, что даёт нам функцию, которая берёт исходную позицию и недетерминированно перемещает коня x раз. Потом просто превращаем исходную позицию в одноэлементный список с помощью функции return и передаём его исходной функции.

Теперь нашу функцию canReachIn3 тоже можно сделать более общей:

canReachIn :: Int –> KnightPos –> KnightPos –> Bool

canReachIn x start end = end `elem` inMany x start

Создание монад

В этом разделе мы рассмотрим пример, показывающий, как тип создаётся, опознаётся как монада, а затем для него создаётся подходящий экземпляр класса Monad. Обычно мы не намерены создавать монаду с единственной целью – создать монаду. Наоборот, мы создаём тип, цель которого – моделировать аспект некоторой проблемы, а затем, если впоследствии мы видим, что этот тип представляет значение с контекстом и может действовать как монада, мы определяем для него экземпляр класса Monad.

Как вы видели, списки используются для представления недетерминированных значений. Список вроде [3,5,9] можно рассматривать как одно недетерминированное значение, которое просто не может решить, чем оно будет. Когда мы передаём список в функцию с помощью операции >>=, это просто создаёт все возможные варианты получения элемента из списка и применения к нему функции, а затем представляет эти результаты также в списке.

Если мы посмотрим на список [3,5,9] как на числа 3, 5, и 9, встречающиеся одновременно, то можем заметить, что нет никакой информации в отношении того, какова вероятность встретить каждое из этих чисел. Что если бы нам было нужно смоделировать недетерминированное значение вроде [3,5,9], но при этом мы бы хотели показать, что 3 имеет 50-процентный шанс появиться, а вероятность появления 5 и 9 равна 25%? Давайте попробуем провести эту работу!

Скажем, что к каждому элементу списка прилагается ещё одно значение: вероятность того, что он появится. Имело бы смысл представить это значение вот так:

[(3,0.5),(5,0.25),(9,0.25)]

Вероятности в математике обычно выражают не в процентах, а в вещественных числах между 0 и 1. Значение 0 означает, что чему-то ну никак не суждено сбыться, а значение 1 – что это что-то непременно произойдёт. Числа с плавающей запятой могут быстро создать путаницу, потому что они стремятся к потере точности, но язык Haskell предлагает тип данных для вещественных чисел. Он называется Rational, и определён он в модуле Data.Ratio. Чтобы создать значение типа Rational, мы записываем его так, как будто это дробь. Числитель и знаменатель разделяются символом %. Вот несколько примеров:

ghci> 1 % 4

1 % 4

ghci> 1 % 2 + 1 % 2

1 % 1

ghci> 1 % 3 + 5 % 4

19 % 12

Первая строка – это просто одна четвёртая. Во второй строке мы складываем две половины, чтобы получить целое. В третьей строке складываем одну третью с пятью четвёртыми и получаем девять двенадцатых. Поэтому давайте выбросим эти плавающие запятые и используем для наших вероятностей тип Rational:

ghci> [(3,1 % 2),(5,1 % 4),(9,1 % 4)]

[(3,1 % 2),(5,1 % 4),(9,1 % 4)]

Итак, 3 имеет один из двух шансов появиться, тогда как 5 и 9 появляются один раз из четырёх. Просто великолепно!

Мы взяли списки и добавили к ним некоторый дополнительный контекст, так что это тоже представляет значения с контекстами. Прежде чем пойти дальше, давайте обернём это в newtype, ибо, как я подозреваю, мы будем создавать некоторые экземпляры.

import Data.Ratio

newtype Prob a = Prob { getProb :: [(a, Rational)] } deriving Show

Это функтор?.. Ну, раз список является функтором, это тоже должно быть функтором, поскольку мы только что добавили что-то в список. Когда мы отображаем список с помощью функции, то применяем её к каждому элементу. Тут мы тоже применим её к каждому элементу, но оставим вероятности как есть. Давайте создадим экземпляр:

instance Functor Prob where

   fmap f (Prob xs) = Prob $ map ((x, p) –> (f x, p)) xs

Мы разворачиваем его из newtype при помощи сопоставления с образцом, затем применяем к значениям функцию f, сохраняя вероятности как есть, и оборачиваем его обратно. Давайте посмотрим, работает ли это:

ghci> fmap negate (Prob [(3,1 % 2),(5,1 % 4),(9,1 % 4)])

Prob {getProb = [(-3,1 % 2),(-5,1 % 4),(-9,1 % 4)]}

Обратите внимание, что вероятности должны давать в сумме 1. Если все эти вещи могут случиться, не имеет смысла, чтобы сумма их вероятностей была чем-то отличным от 1. Думаю, выпадение монеты на решку 75% раз и на орла 50% раз могло бы происходить только в какой-то странной Вселенной.

А теперь главный вопрос: это монада? Учитывая, что список является монадой, похоже, и это должно быть монадой. Во-первых, давайте подумаем о функции return. Как она работает со списками? Она берёт значение и помещает его в одноэлементный список. Что здесь происходит? Поскольку это должен быть минимальный контекст по умолчанию, она тоже должна создавать одноэлементный список. Что же насчёт вероятности? Вызов выражения return x должен создавать монадическое значение, которое всегда представляет x как свой результат, поэтому не имеет смысла, чтобы вероятность была равна 0. Если оно всегда должно представлять это значение как свой результат, вероятность должна быть равна 1!

А что у нас с операцией >>=? Выглядит несколько мудрёно, поэтому давайте воспользуемся тем, что для монад выражение m >>= f всегда равно выражению join (fmap f m), и подумаем, как бы мы разгладили список вероятностей списков вероятностей. В качестве примера рассмотрим список, где существует 25-процентный шанс, что случится именно 'a' или 'b'. И 'a', и 'b' могут появиться с равной вероятностью. Также есть шанс 75%, что случится именно 'c' или 'd'. То есть 'c' и 'd' также могут появиться с равной вероятностью. Вот рисунок списка вероятностей, который моделирует данный сценарий:

Каковы шансы появления каждой из этих букв? Если бы мы должны были изобразить просто четыре коробки, каждая из которых содержит вероятность, какими были бы эти вероятности? Чтобы узнать это, достаточно умножить каждую вероятность на все вероятности, которые в ней содержатся. Значение 'a' появилось бы один раз из восьми, как и 'b', потому что если мы умножим одну четвёртую на одну четвёртую, то получим одну восьмую. Значение 'c' появилось бы три раза из восьми, потому что три четвёртых, умноженные на одну вторую, – это три восьмых. Значение 'd' также появилось бы три раза из восьми. Если мы сложим все вероятности, они по-прежнему будут давать в сумме единицу.