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

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

ghci> powerset [1,2,3]

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

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

Функция foldM

Монадическим аналогом функции 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.

Мы реализовали наш калькулятор обратной польской записи, получая строку вроде "1 3 + 2 *" и разделяя её на слова, чтобы получить нечто подобное: ["1","3","+","2","*"]. Затем мы сворачивали этот список, начиная с пустого стека и используя бинарную функцию свёртки, которая добавляет числа в стек либо манипулирует числами на вершине стека, чтобы складывать их или делить и т. п.

Вот это было основным телом нашей функции:

import Data.List

solveRPN :: String –> Double

solveRPN = head . foldl foldingFunction [] . words

Мы превратили выражение в список строк и свернули его, используя нашу функцию свёртки. Затем, когда у нас в стеке остался лишь один элемент, мы вернули этот элемент в качестве ответа. Вот такой была функция свёртки:

foldingFunction :: [Double] –> String –> [Double]

foldingFunction (x:y:ys) "*" = (y * x):ys

foldingFunction (x:y:ys) "+" = (y + x):ys