Изучай Haskell во имя добра! (Липовача) - страница 277

А что у нас с операцией >>>=? Выглядит несколько мудрёно, поэтому давайте воспользуемся тем, что для монад выражение >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