Функция filterM

We use cookies. Read the Privacy and Cookie Policy

Функция filter – это просто хлеб программирования на языке Haskell (при том что функция map – масло). Она принимает предикат и список, подлежащий фильтрации, а затем возвращает новый список, в котором сохраняются только те элементы, которые удовлетворяют предикату. Её тип таков:

filter :: (a –> Bool) –> [a] –> [a]

Предикат берёт элемент списка и возвращает значение типа Bool. А вдруг возвращённое им значение типа Bool было на самом деле монадическим? Что если к нему был приложен контекст?.. Например, каждое значение True или False, произведённое предикатом, имело также сопутствующее моноидное значение вроде ["Принято число 5"] или ["3 слишком мало"]? Если бы это было так, мы бы ожидали, что к результирующему списку тоже прилагается журнал всех журнальных значений, которые были произведены на пути. Поэтому если бы к списку, возвращённому предикатом, возвращающим значение типа Bool, был приложен контекст, мы ожидали бы, что к результирующему списку тоже прикреплён некоторый контекст. Иначе контекст, приложенный к каждому значению типа Bool, был бы утрачен.

Функция filterM из модуля Control.Monad делает именно то, что мы хотим! Её тип таков:

filterM :: (Monad m) => (a –> m Bool) –> [a] –> m [a]

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

Давайте возьмём список и оставим только те значения, которые меньше 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],[]]

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