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