>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 делает то же самое, только она принимает бинарную функцию, производящую монадическое значение, и сворачивает список с её использованием. Неудивительно, что результирующее значение тоже является монадическим. Тип функции