Композиция монадических функций

Когда мы говорили о законах монад в главе 13, вы узнали, что функция <=< очень похожа на композицию, но вместо того чтобы работать с обычными функциями типа a –> b, она работает с монадическими функциями типа a –> m b. Вот пример:

ghci> let f = (+1) . (*100)

ghci> f 4

401

ghci> let g = (x –> return (x+1)) <=< (x –> return (x*100))

ghci> Just 4 >>= g

Just 401

В данном примере мы сначала произвели композицию двух обычных функций, применили результирующую функцию к 4, а затем произвели композицию двух монадических функций и передали результирующей функции Just 4 с использованием операции >>=.

Если у вас есть набор функций в списке, вы можете скомпоновать их все в одну большую функцию, просто используя константную функцию id в качестве исходного аккумулятора и функцию (.) в качестве бинарной. Вот пример:

ghci> letf = foldr (.) id [(+1),(*100),(+1)]

ghci> f 1

201

Функция f принимает число, а затем прибавляет к нему 1, умножает результат на 100 и прибавляет к этому 1.

Мы можем компоновать монадические функции так же, но вместо обычной композиции используем операцию <=<, а вместо id – функцию return. Нам не требуется использовать функцию foldM вместо foldr или что-то вроде того, потому что функция <=< гарантирует, что композиция будет происходить монадически.

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

in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight

И чтобы проверить, может ли конь пройти от start до end в три хода, мы сделали следующее:

canReachIn3 :: KnightPos –> KnightPos –> Bool

canReachIn3 start end = end `elem` in3 start

Используя композицию монадических функций, можно создать функцию вроде in3, только вместо произведения всех позиций, которые может занимать конь после совершения трёх ходов, мы сможем сделать это для произвольного количества ходов. Если вы посмотрите на in3, то увидите, что мы использовали нашу функцию moveKnight трижды, причём каждый раз применяли операцию >>=, чтобы передать ей все возможные предшествующие позиции. А теперь давайте сделаем её более общей. Вот так:

import Data.List

inMany :: Int –> KnightPos –> [KnightPos]

inMany x start = return start >>= foldr (<=<) return (replicate x moveKnight)

Во-первых, мы используем функцию replicate, чтобы создать список, который содержит x копий функции moveKnight. Затем мы монадически компонуем все эти функции в одну, что даёт нам функцию, которая берёт исходную позицию и недетерминированно перемещает коня x раз. Потом просто превращаем исходную позицию в одноэлементный список с помощью функции return и передаём его исходной функции.

Теперь нашу функцию canReachIn3 тоже можно сделать более общей:

canReachIn :: Int –> KnightPos –> KnightPos –> Bool

canReachIn x start end = end `elem` inMany x start