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

Теперь у нас есть всё, что нам нужно. Мы можем написать экземпляр класса 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, так что это не повлияло бы на контекст.

2. Второе правило утверждает, что выражение m >> returnничем не отличается от m. Для нашего примера доказательство того, что выражение m >> returnравно просто m, аналогично доказательству первого закона.

3. Третий закон утверждает, что выражение f <=< (g <=< h)должно быть аналогично выражению (f <=< g) <=< h. Это тоже верно, потому что данное правило выполняется для списковой монады, которая составляет основу для монады вероятностей, и потому что умножение ассоциативно. 1 % 2 * (1 % 3 * 1 % 5)равно (1 % 2 * 1 % 3) * 1 % 5.

Теперь, когда у нас есть монада, что мы можем с ней делать? Она может помочь нам выполнять вычисления с вероятностями. Мы можем обрабатывать вероятностные события как значения с контекстами, а монада вероятностей обеспечит отражение этих вероятностей в вероятностях окончательного результата.

Скажем, у нас есть две обычные монеты и одна монета, с одной стороны налитая свинцом: она поразительным образом выпадает на решку девять раз из десяти и на орла – лишь один раз из десяти. Если мы подбросим все монеты одновременно, какова вероятность того, что все они выпадут на решку? Во-первых, давайте создадим значения вероятностей для подбрасывания обычной монеты и для монеты, налитой свинцом:

data Coin = Heads | Tails deriving (Show, Eq)

coin :: Prob Coin

coin = Prob [(Heads,1 % 2),(Tails,1 % 2)]

loadedCoin :: Prob Coin

loadedCoin = Prob [(Heads,1 % 10),(Tails,9 % 10)]

И наконец, действие по подбрасыванию монет:

import Data.List (all)

flipThree :: Prob Bool

flipThree = do

a <���– coin

b <���– coin

c <���– loadedCoin

return (all (==Tails) [a,b,c])

При попытке запустить его видно, что вероятность выпадения решки у всех трёх монет не так высока, даже несмотря на жульничество с нашей налитой свинцом монетой:

ghci> getProb flipThree

[(False,1 % 40),(False,9 % 40),(False,1 % 40),(False,9 % 40),

(False,1 % 40),(False,9 % 40),(False,1 % 40),(True,9 % 40)]

Все три приземлятся решкой вверх 9 раз из 40, что составляет менее 25%!.. Видно, что наша монада не знает, как соединить все исходы False, где все монеты не приземляются решкой вверх, в один исход. Впрочем, это не такая серьёзная проблема, поскольку написание функции для вставки всех одинаковых исходов в один исход довольно просто (это упражнение я оставляю вам в качестве домашнего задания).

В этом разделе мы перешли от вопроса («Что если бы списки также содержали информацию о вероятностях?») к созданию типа, распознанию монады и, наконец, созданию экземпляра и выполнению с ним некоторых действий. Думаю, это очаровательно! К этому времени у вас уже должно сложиться довольно неплохое понимание монад и их сути.

Хотя чистота языка Haskell даёт море преимуществ, вместе с тем он заставляет нас решать некоторые проблемы не так, как мы решали бы их в нечистых языках.

Из-за прозрачности ссылок одно значение в языке Haskell всё равно что другое, если оно представляет то же самое. Поэтому если у нас есть дерево, заполненное пятёрками (или, может, пятернями?), и мы хотим изменить одну из них на шестёрку, мы должны каким-то образом понимать, какую именно пятёрку в нашем дереве мы хотим изменить. Нам нужно знать, где в нашем дереве она находится. В нечистых языках можно было бы просто указать, где в памяти находится пятёрка, и изменить её. Но в языке Haskell одна пятёрка – всё равно что другая, поэтому нельзя проводить различие исходя из их расположения в памяти.