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

Давайте возьмём список и оставим только те значения, которые меньше 4. Для начала мы используем обычную функцию filter:

ghci> filter (\x –> x < 4) [9,1,5,2,10,3]

[1,2,3]

Это довольно просто. Теперь давайте создадим предикат, который помимо представления результата Trueили Falseтакже предоставляет журнал своих действий. Конечно же, для этого мы будем использовать монаду Writer:

keepSmall :: Int –> Writer [String] Bool

keepSmall x

| x < 4 = do

tell ["Сохраняем " ++ show x]

return True

| otherwise = do

tell [show x ++ " слишком велико, выбрасываем"]

return False

Вместо того чтобы просто возвращать значение типа Bool, функция возвращает значение типа Writer [String] Bool. Это монадический предикат. Звучит необычно, не так ли? Если число меньше числа 4, мы сообщаем, что оставили его, а затем возвращаем значение True.

Теперь давайте передадим его функции filterMвместе со списком. Поскольку предикат возвращает значение типа Writer, результирующий список также будет значением типа Writer.

ghci> fst $ runWriter $ filterM keepSmall [9,1,5,2,10,3]

[1,2,3]

Проверяя результат результирующего значения монады Writer, мы видим, что всё в порядке. Теперь давайте распечатаем журнал и посмотрим, что у нас есть:

ghci> mapM_ putStrLn $ snd $ runWriter $ filterM keepSmall [9,1,5,2,10,3]

9 слишком велико, выбрасываем

Сохраняем 1

5 слишком велико, выбрасываем

Сохраняем 2

10 слишком велико, выбрасываем

Сохраняем 3

Итак, просто предоставляя монадический предикат функции filterM, мы смогли фильтровать список, используя возможности применяемого нами монадического контекста.

Очень крутой трюк в языке Haskell – использование функции filterMдля получения множества-степени списка (если мы сейчас будем думать о нём как о множестве). Множеством – степенью некоторого множества называется множество всех подмножеств данного множества. Поэтому если у нас есть множество вроде [1,2,3], его множество-степень включает следующие множества:

[1,2,3]

[1,2]

[1,3]

[1]

[2,3]

[2]

[3]

[]

Другими словами, получение множества-степени похоже на получение всех сочетаний сохранения и выбрасывания элементов из множества. Например, [2,3]– это исходное множество с исключением числа 1; [1,2]– это исходное множество с исключением числа 3и т. д.

Чтобы создать функцию, которая возвращает множество-степень какого-то списка, мы положимся на недетерминированность. Мы берём список [1,2,3], а затем смотрим на первый элемент, который равен 1, и спрашиваем себя: «Должны ли мы его сохранить или отбросить?» Ну, на самом деле мы хотели бы сделать и то и другое. Поэтому мы отфильтруем список и используем предикат, который сохраняет и отбрасывает каждый элемент из списка недетерминированно. Вот наша функция powerset:

powerset :: [a] –> [[a]]

powerset xs = filterM (\x –> [True, False]) xs

Стоп, это всё?! Угу! Мы решаем отбросить и оставить каждый элемент независимо от того, что он собой представляет. У нас есть недетерминированный предикат, поэтому результирующий список тоже будет недетерминированным значением – и потому будет списком списков. Давайте попробуем:

ghci> powerset [1,2,3]

[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

Вам потребуется немного поразмыслить, чтобы понять это. Просто воспринимайте списки как недетерминированные значения, которые толком не знают, чем быть, поэтому решают быть сразу всем, – и эту концепцию станет проще усвоить!

Монадическим аналогом функции foldlявляется функция foldM. Если вы помните свои свёртки из главы 5, вы знаете, что функция foldlпринимает бинарную функцию, исходный аккумулятор и сворачиваемый список, а затем сворачивает его слева в одно значение, используя бинарную функцию. Функция foldMделает то же самое, только она принимает бинарную функцию, производящую монадическое значение, и сворачивает список с её использованием. Неудивительно, что результирующее значение тоже является монадическим. Тип функции foldlтаков:

foldl :: (a –> b –> a) –> a –> [b] –> a

Тогда как функция foldMимеет такой тип:

foldM :: (Monad m) => (a –> b –> m a) –> a –> [b] –> m a

Значение, которое возвращает бинарная функция, является монадическим, поэтому результат всей свёртки тоже является монадическим. Давайте сложим список чисел с использованием свёртки:

ghci> foldl (\acc x –> acc + x) 0 [2,8,3,1]

14

Исходный аккумулятор равен 0, затем к аккумулятору прибавляется 2, что даёт в результате новый аккумулятор со значением 2. К этому аккумулятору прибавляется 8, что даёт в результате аккумулятор равный 10и т. д. Когда мы доходим до конца, результатом является окончательный аккумулятор.

А ну как мы захотели бы сложить список чисел, но с дополнительным условием: если какое-то число в списке больше 9, всё должно окончиться неудачей? Имело бы смысл использовать бинарную функцию, которая проверяет, больше ли текущее число, чем 9. Если больше, то функция оканчивается неудачей; если не больше – продолжает свой радостный путь. Из-за этой добавленной возможности неудачи давайте заставим нашу бинарную функцию возвращать аккумулятор Maybeвместо обычного.

Вот бинарная функция:

binSmalls :: Int –> Int –> Maybe Int

binSmalls acc x

| x > 9 = Nothing

| otherwise = Just (acc + x)

Поскольку наша бинарная функция теперь является монадической, мы не можем использовать её с обычной функцией foldl; следует использовать функцию foldM. Приступим:

ghci> foldM binSmalls 0 [2,8,3,1]

Just 14

ghci> foldM binSmalls 0 [2,11,3,1]

Nothing

Клёво! Поскольку одно число в списке было больше 9, всё дало в результате значение Nothing. Свёртка с использованием бинарной функции, которая возвращает значение Writer, – тоже круто, потому что в таком случае вы журналируете что захотите по ходу работы вашей свёртки.

Решая задачу реализации калькулятора для обратной польской записи в главе 10, мы отметили, что он работал хорошо до тех пор, пока получаемые им входные данные имели смысл. Но если что-то шло не так, это приводило к аварийному отказу всей нашей программы. Теперь, когда мы знаем, как сделать уже существующий код монадическим, давайте возьмём наш калькулятор и добавим в него обработку ошибок, воспользовавшись монадой Maybe.