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

Когда вы знакомились со списковой монадой в главе 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: