Изучай Haskell во имя добра!

Во-первых, мы используем функцию 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)]}