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

Мы можем компоновать монадические функции так же, но вместо обычной композиции используем операцию <=<,а вместо 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!