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

Обратите внимание, что вероятности должны давать в сумме 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' также появилось бы три раза из восьми. Если мы сложим все вероятности, они по-прежнему будут давать в сумме единицу.

Вот эта ситуация, выраженная в форме списка вероятностей:

thisSituation :: Prob (Prob Char)

thisSituation = Prob

   [(Prob [('a',1 % 2),('b',1 % 2)], 1 % 4)

   ,(Prob [('c',1 % 2),('d',1 % 2)], 3 % 4)

   ]

Обратите внимание, её тип – Prob (Prob Char). Поэтому теперь, когда мы поняли, как разгладить вложенный список вероятностей, всё, что нам нужно сделать, – написать для этого код. Затем мы можем определить операцию >>= просто как join (fmap f m), и заполучим монаду! Итак, вот функция flatten, которую мы будем использовать, потому что имя join уже занято:

flatten :: Prob (Prob a) –> Prob a

flatten (Prob xs) = Prob $ concat $ map multAll xs

   where multAll (Prob innerxs, p) = map (\(x, r) –> (x, p*r)) innerxs

Функция multAll принимает кортеж, состоящий из списка вероятностей и вероятности p, которая к нему приложена, а затем умножает каждую внутреннюю вероятность на p, возвращая список пар элементов и вероятностей. Мы отображаем каждую пару в нашем списке вероятностей с помощью функции multAll, а затем просто разглаживаем результирующий вложенный список.

Теперь у нас есть всё, что нам нужно. Мы можем написать экземпляр класса Monad!

instance Monad Prob where

   return x = Prob [(x,1 % 1)]

   m >>= f = flatten (fmap f m)

   fail _ = Prob []

Поскольку мы уже сделали всю тяжелую работу, экземпляр очень прост. Мы определили функцию fail, которая такова же, как и для списков, поэтому если при сопоставлении с образцом в выражении do происходит неудача, неудача случается в контексте списка вероятностей.

Важно также проверить, что для только что созданной нами монады выполняются законы монад:

1. Первое правило говорит, что выражение return x >>= f должно равняться выражению f x. Точное доказательство было бы довольно громоздким, но нам видно, что если мы поместим значение в контекст по умолчанию с помощью функции return, затем отобразим это с помощью функции, используя fmap, а потом отобразим результирующий список вероятностей, то каждая вероятность, являющаяся результатом функции, была бы умножена на вероятность 1 % 1, которую мы создали с помощью функции return, так что это не повлияло бы на контекст.