Haskell/Monad transformers

Материал из Викиучебника — открытых книг для открытого мира
Monad transformers (Solutions)
Monads

Шаблон:Haskell chapter/Monads

К этому моменту вы должны были предварительно уяснить понятие монады, а также то, что различные монады используются еще для: IO для «нечистых» функций, Maybe для значений, которые могут быть или нет, и так далее. С помощью монад, обеспечивающих такую полезную функциональность общего назначения, очень естественно, что порой мы хотели бы использовать возможности нескольких монад сразу — например, функция, которая использует и IO, и обработку исключений Maybe. Конечно, мы можем использовать такой тип как IO (Maybe a), но это заставляет нас делать сопоставление с образцом в do-блоках, чтобы извлечь необходимые значения: однако, фишка монад была также в том, чтобы избавиться от этого.

Итак, рассмотрим монадные трансформеры: специальные типы, которые позволяют нам комбинировать две монады в одной, но разделяющие поведение обеих. Начнем с примера, чтобы проиллюстрировать, почему трансформеры полезны и показать, как они работают.

Проверка пароля[править]

Рассмотрим обычную проблему из реальной жизни ИТ-специалистов всего мира: составим программу, запрашивающую у пользователей пароли, которые трудно угадать. Типичная стратегия — заставить пользователя ввести пароль не короче минимальной длины, содержащий по крайней мере одну букву и одну цифру (и отвечающий прочим раздражающим требованиям).

Функция получения пароля от пользователя на Haskell может выглядеть следующим образом:

getPassphrase :: IO (Maybe String)
getPassphrase = do s <- getLine
                   if isValid s then return $ Just s
                                else return Nothing

-- Проверку правильности мы можем сделать какой захотим.
isValid :: String -> Bool
isValid s = length s >= 8
            && any isAlpha s
            && any isNumber s
            && any isPunctuation s

Прежде всего getPassphrase это действие ввода/вывода, возвращающее монаду IO, потому что она работает с пользовательским вводом. Кроме того мы используем Maybe, потому что хотим возвращать Nothing, если пароль не проходит проверку isValid. Заметим, однако, что использовать Maybe как монаду мы здесь по сути не будем: do-блок находится в монаде IO, и нам просто повезло получить return с Maybe-значением внутри.

Но трансформеры монад упрощают нам код не только самой функции getPassphrase, но и тех мест, где она используется. Дальше в нашей программе сбора паролей может быть вот что:

askPassphrase :: IO ()
askPassphrase = do putStrLn "Insert your new passphrase:"
                   maybe_value <- getPassphrase
                   case maybe_value of
                       Just value -> do putStrLn "Storing in database..."  -- do stuff
                       Nothing -> putStrLn "Passphrase invalid."

Мы одной строчкой получаем переменную maybe_value-переменной, а дальше проверяем, в порядке наш пароль или нет.

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

Простой монадный трансформер: MaybeT[править]

Для упрощения функции getPassphrase и использующего её кода мы определим монадный трансформер, который даёт монаде IO некоторые характеристики монады Maybe. Мы будем называть его MaybeT, следуя соглашению, что имя монадного трансформера составляется из названия монады, чьи характеристики он обеспечивает, и буквы «T».

MaybeT это обертка вокруг m (Maybe a), где m может быть любой монадой (в нашем примере это IO):

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }

Здесь определён конструктор типа MaybeT, параметризуемый типом m, с конструктором данных, который тоже называется MaybeT, и вспомогательной функцией runMaybeT, обеспечивающей доступ к содержимому типа.

Идея монадного трансформера — в создании монады, ведущей себя как другая монада, так что MaybeT m нужно сделать экземпляром класса Monad:

instance Monad m => Monad (MaybeT m) where
  return  = MaybeT . return . Just

Функция return оборачивает переданное ей значение (имя которого мы не указали, потому что используем частичное применение) в монаду Maybe с помощью Just, а потом в монаду m (чем бы она ни была) с помощью return; результат передаётся конструктору MaybeT. Можно было бы написать return = MaybeT . return . return, но понять такой код было бы ещё сложнее.

  -- Тип функции (>>=), определённой на MaybeT m:
  -- (>>=) :: MaybeT m a -> (a -> MaybeT m b) -> MaybeT m b
  x >>= f = MaybeT $ do maybe_value <- runMaybeT x
                        case maybe_value of
                           Nothing    -> return Nothing
                           Just value -> runMaybeT $ f value

Как это обычно бывает с монадами, для понимания работы MaybeT важнее всего разобраться, как работает оператор связывания >>=. Рассмотрим, что он делает, шаг за шагом, начиная с первой строки блока do.

  • Первым делом мы извлекаем из x значение типа m (Maybe a) с помощью функции runMaybeT; соответственно, весь блок do будет работать с монадой m.
  • В той же строке мы извлекаем значение Maybe a из монады m и помещаем его в maybe_value с помощью оператора <-.
  • Выражение case проверяет значение maybe_value и:
    • …если это Nothing, возвращает Nothing, завёрнутый в m с помощью return;
    • …eсли это Just value, применяет к value функцию f; так как функция f уже возвращает значение типа MaybeT m b, нам нужно извлечь из него значение типа m b с помощью runMaybeT — ведь блок do работает с монадой m, и из всех его веток мы должны вернуть именно её.
  • А в конце мы завернём обратно полученное внутри блока do значение типа m (Maybe b) с помощью конструктора MaybeT.

Всё это может смотреться сложновато, но за вычетом всех этих разворачиваний и заворачиваний по сути здесь происходит то же, что в хорошо знакомом нам >>= для Maybe:

-- (>>=) для монады Maybe
    maybe_value >>= f = case maybe_value of
                            Nothing -> Nothing
                            Just value -> f value

Вас может удивить, что мы разворачиваем наш тип с помощью runMaybeT внутри блока do только затем, чтобы сразу же завернуть его результат обратно с помощью MaybeT; но дело в том, что в этом месте мы можем воспользоваться синтаксисом do только для монады m, потому что блок do использует оператор >>=, а для MaybeT он, понятно, ещё не определён — как раз его определением мы здесь и заняты.

Как обычно, для нашего типа нужно породить экземпляры классов-предков класса MonadApplicative и Functor:

instance Monad m => Applicative (MaybeT m) where
    pure = return
    (<*>) = ap

instance Monad m => Functor (MaybeT m) where
    fmap = liftM

Кроме того, будет удобно, если MaybeT m будет экземпляром ещё пары классов типов:

instance Monad m => Alternative (MaybeT m) where
    empty   = MaybeT $ return Nothing
    x <|> y = MaybeT $ do maybe_value <- runMaybeT x
                          case maybe_value of
                               Nothing    -> runMaybeT y
                               Just _     -> return maybe_value

instance Monad m => MonadPlus (MaybeT m) where 
    mzero = empty
    mplus = (<|>)

instance MonadTrans MaybeT where
    lift = MaybeT . (liftM Just)

В классе MonadTrans определяется функция lift, так что теперь можно просто брать функции, работающие с монадой m, поднимать их в монаду MaybeT m и работать с ними в блоках do как с функциями для монады MaybeT m. Что же до Alternative и MonadPlus, то раз уж для Maybe определены экземпляры этих классов, логично определить их и для MaybeT m тоже.

Упрощаем проверку паролей[править]

Монадный трансформер MaybeT позволяет нам переписать определённую выше функцию проверки паролей так:

getPassphrase :: MaybeT IO String
getPassphrase = do s <- lift getLine
                   guard (isValid s) -- функция guard определена для класса Alternative.
                   return s

askPassphrase :: MaybeT IO ()
askPassphrase = do lift $ putStrLn "Insert your new passphrase:"
                   value <- getPassphrase
                   lift $ putStrLn "Storing in database..."

Код стал заметно проще, особенно в функции askPassphrase. Но главное — теперь не надо вручную проверять, равен результат Nothing или Just: оператор >>= делает это за нас.

Обратите внимание, как мы используем lift, чтобы заставить функции getLine и putStrLn работать с монадой MaybeT IO. А так как для MaybeT IO определён экземпляр класса Alternative, о проверке пароля позаботится выражение guard, которое вернёт empty (т.е. IO Nothing) для слишком слабых паролей.

Заодно благодаря MonadPlus теперь очень просто до бесконечности требовать у пользователя подходящий пароль:

askPassphrase :: MaybeT IO ()
askPassphrase = do lift $ putStrLn "Insert your new passphrase:"
                 value <- msum $ repeat getPassphrase
                 lift $ putStrLn "Storing in database..."

Изобилие трансформеров[править]

Модуль пакета transformers обеспечивает трансформеры для многих общих монад (MaybeT, например, может быть найдена в Шаблон:Haskell lib). Они определены в соответствии с их нетрансформерской версией; то есть, реализация в базовом та же самая, только с дополнительными обертками и развертками, необходимыми для ввинчивания в другую монаду.

Выберем произвольный пример, ReaderT Env IO String -- вычисление, которое вовлечет считываемое значение из некоторого окружения типа Env (семантика из Reader, базовой монады) и выполняет некоторое IO (действие) для того, чтобы получить значение типа String. Так как операторы bind и return отражают семантику базовой монады, do-блок типа ReaderT Env IO String будет с внешней стороны похож на do-блок монады Reader; главная разница будет в том, что IO-действия становятся тривиальными для встраивания при использовании функции lift.

Манипуляции с типами[править]

Мы видели, что конструктор типа для MaybeT является оболочкой для значения типа Maybe во внутренней монаде, и поэтому соответствующая функция доступа runMaybeT дает нам значение типа m (Maybe a) — то есть, значение базовой монады возвращенную во внутреннюю монаду. Аналогичным образом, мы имеем

runListT :: ListT m a -> m [a]

и

runErrorT :: ErrorT e m a -> m (Either e a)

для трансформеров списков (list) и ошибок (error).

Все же, не все трансформеры связаны с базовой монадой таким образом. Монады Writer, Reader, State и Cont объединяет то, что в отличие от базовых монады в примерах выше, они не имеют ни нескольких конструкторов, ни конструкторов с несколькими аргументами. По этой причине, у них есть функции run..., которые действуют как простые развертыватели (unwrappers) аналогично соответственным run...T из версий трансформера. В приведенной ниже таблице показаны результаты типов функций run... и run...T в каждом конкретном случае, что может рассматриваться как типы обернутые базовой и трансформированной монадой соответственно.

Base Monad Transformer Original Type
(«wrapped» by base)
Combined Type
(«wrapped» by transformed)
Writer WriterT (a, w) m (a, w)
Reader ReaderT r -> a r -> m a
State StateT s -> (a, s) s -> m (a, s)
Cont ContT (a -> r) -> r (a -> m r) -> m r

Первое, на что нужно обратить внимание, это то, что базовые монады нигде не было видно в комбинированной типов. Это очень естественно, так как без конструкторы интересны (например, те для Может быть, или списки) нет никаких причин, чтобы сохранить базовый тип монады после разворачивания преобразованной монады. . Кроме того, в трех последних случаях у нас есть функция типа завернутые StateT , например, превращает государственные преобразования функций вида с -> (A, S) в государственно-преобразования функций вида с -> M (, с), так что только тип результата функции завернутые идет во внутренний монады. ReaderT аналогична, но не ContT : в связи с семантикой Cont (продолжение монады) результат обоих типов завернутые функции и ее функциональное Аргумент должен быть таким же, так что трансформатор ставит как во внутреннюю монады. Что эти примеры показывают, что в целом нет никакой волшебной формулы для создания трансформатора версия монады-формы каждого трансформера, зависит от того, что имеет смысл в контексте его не-трансформатор типа.

Подъем[править]

Функция lift, которую мы впервые представили во введении, очень важна для повседневного использования трансформеров; и поэтому мы посвятим несколько слов ей.

liftM[править]

Начнем с того, что строго говоря, она не из темы монадных трансформеров. liftM — черезвычайно полезная функция в стандартной библиотеке со следующей сигнатурой:

liftM :: Monad m => (a1 -> r) -> m a1 -> m r

liftM применяет функцию (a1 -> r) к значению в рамках (внутри) монады m. Если вы предпочитаете бесточечную запись, она может превратить обычную функцию в такую, которая действует внутри m — и это как раз то, что подразумевается под поднятием в монаду.

Давайте посомтрим, как liftM используется. Следующие фрагменты обозначают одно и то же.

do notation liftM liftM as an operator
do x <- monadicValue
   return (f x)
liftM f monadicValue
f `liftM` monadicValue

Третий пример, в котором мы используем liftM как оператор, предлагает интересную точку зрения на liftM: это просто монадическая версия ($)!

non monadic monadic
f $ value
f `liftM` monadicValue
Упражнения
  1. Напишите реализацию для liftM.

lift[править]

Когда мы используем монады, созданные с помощью монадных трансформеров, мы можем избежать явного управления внутренними монадными типами, и в результате получаем более ясный и простой код. Вместо создания дополнительных do-блоков внутри вычисления для манипуляции значениями во внутренней монаде, мы можем использовать поднятые операции, чтобоы перенести функции из внутренней монады в комбинированную монаду.

С liftM мы увидели, что сущность поднятия — перефразируя документацию — в продвижении чего-то в монаду. Функция lift, доступная для всех монадных трансформеров, выполняет разный тип поднятия: она продвигает вычисление из внутренней монады в комбинированную монаду. Функция lift определена как единственный метод класса MonadTrans в Шаблон:Haskell lib.

class MonadTrans t where
    lift :: (Monad m) => m a -> t m a

Имеется вариант lift, специфичный для IO и называемый liftIO, который является единственным методом класса MonadIO в Шаблон:Haskell lib.

class (Monad m) => MonadIO m where
   liftIO :: IO a -> m a

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

Реализация lift[править]

Реализация lift как правило довольно прямолинейна (проста). Рассмотрим трансформер MaybeT:

instance MonadTrans MaybeT where
    lift m = MaybeT (m >>= return . Just)

Мы начинаем с монадическим значением внутренней монады — средним слоем, если вы предпочитаете аналогию с сэндвичем. Используя оператор bind и конструктор типа для базовой монады, мы плавно сдвигаем (скатываем, намазываем ??) нижний слой (базовую монаду) под средний слой. В конце, мы помещаем верхний срез нашего сэндвича с помощью конструктора MaybeT. Таким образом, используя функцию lift, мы трансформировали нижний кусок начинки сэндвича в подлинно трехслойный монадический сэндвич. Отметим, что как в реализации класса Monad, и оператор bind, и общий (основной) оператор return работают в границах внутренней монады.

Упражнения
  1. Почему функция lift была определена отдельно для каждой монады, тогда как функция liftM может быть определена универсальным способом?
  2. Реализуйте функцию lift для трансформера ListT.
  3. Как бы подняли обычную функцию в монадный трансформер? Подсказка: очень легко.

Реализация трансформеров[править]

Для того, чтобы развить лучшее понимание работы трансформеров, мы обсудим две реализации в стандартных библиотеках.

Трансформер List[править]

Также как с трансформером Maybe, мы начнем с создания конструктора типа, который принимает один аргумент:

newtype ListT m a = ListT { runListT :: m [a] }

Реализация монады ListT m поразительно похожа на свою «кузину», монаду списков. Мы делаем те же самые операции внутри внутренней монады m, пакуем и распаковываем монадический сэндвич.

List ListT
instance Monad [] where
    xs >>= f =

        let yss = map f xs
        in concat yss
instance (Monad m) => Monad (ListT m) where
    tm >>= f = ListT $ runListT tm
                 >>= \xs -> mapM (runListT . f) xs
                   >>= \yss -> return (concat yss)
Упражнения
  1. Препарируйте оператор bind для монады (ListT m). К примеру, почему у нас уже есть mapM и return?
  2. Сейчас когда вы увидели два простых монадных трансформера, напишите монадный трансформер IdentityT, который был бы трансформирующей кузиной монады Identity.
  3. Будет ли IdentityT SomeMonad эквивалентна SomeMonadT Identity для заданной монады и ее кузины-трансформера?

Трансформер State[править]

В прошлый раз мы пристально рассмотрели реализацию двух простых монадных трансформеров, MaybeT и ListT, совершив обходной путь, чтобы обсудить подъем из (простой) монады в ее вариант-трансформер. Теперь, соединим две идеи вместе, внимательно рассмотрев реализацию одного из наиболее интересных трансформеров в стандартной библиотеке, StateT. Изучение этого трансформера сотворит озарение в понимании механизма трансформеров, которое вы сможете призвать впоследствии, когда будуте использовать монадные трансформеры в вашем коде. Прежде чем продолжить, вам может быть понадобиться освежить в памяти или просмотреть State monad.

Как и монада State могла быть построена определением newtype State s a = State { runState :: (s -> (a,s)) }[1] Трансформер StateT создан определением

newtype StateT s m a = StateT { runStateT :: (s -> m (a,s)) }

State s является воплощением как класса Monad, так и класса MonadState s (который обеспечивает get и put), так что StateT s m должна быть членом классов Monad и MonadState s. Более того, если m является воплощением MonadPlus, StateT s m также должна быть членом MonadPlus.

Определим StateT s m как воплощение Monad:

State StateT
newtype State s a =
  State { runState :: (s -> (a,s)) }

instance Monad (State s) where
  return a        = State $ \s -> (a,s)
  (State x) >>= f = State $ \s ->
    let (v,s') = x s
    in runState (f v) s'
newtype StateT s m a =
  StateT { runStateT :: (s -> m (a,s)) }

instance (Monad m) => Monad (StateT s m) where
  return a         = StateT $ \s -> return (a,s)
  (StateT x) >>= f = StateT $ \s -> do
    (v,s') <- x s          -- get new value and state
    runStateT (f v) s'     -- pass them to f

Наше определение return использует функцию return внутренней монады, и оператор связывания использует do-блок, чтобы выполнить вычисление во внутренней монаде.

Мы также хотим декларировать все комбинированные монады, которые используют трансформер StateT, как воплощения класса MonadState, так что мы дадим определения get и put:

instance (Monad m) => MonadState s (StateT s m) where
  get   = StateT $ \s -> return (s,s)
  put s = StateT $ \_ -> return ((),s)

Наконец, мы хотим декларировать все комбинированные монады, в которых используется StateT с воплощением MonadPlus, как воплощения класса MonadPlus:

instance (MonadPlus m) => MonadPlus (StateT s m) where
  mzero = StateT $ \s -> mzero
  (StateT x1) `mplus` (StateT x2) = StateT $ \s -> (x1 s) `mplus` (x2 s)

Последним шагом сделаем наш монадный трансформер полностью интегрированным с классом монад Haskell’а — для этого сделаем StateT s воплощением класса MonadTrans, обеспечив функцию lift:

instance MonadTrans (StateT s) where
  lift c = StateT $ \s -> c >>= (\x -> return (x,s))

Функция lift создает функцию, изменяющую состояние, StateT, которая связывает вычисление во внутренней монаде с функцией, пакующей результат со входным состоянием. Результат в том, если для воплощения мы применяем StateT к монаде the List, функция, которая возвращает список (то есть, вычисление в монаде List) может быть поднято вовнутрь StateT s [], где оно станет функцией, которая возвращает StateT (s -> [(a,s)]). Таким образом, поднятое вычисление производит множественные пары (значение, состояние) из его внутреннего состояния. Эффект выразится в «разветвлении» вычисления в StateT, создавая разные ветви для разных значений в списке, возвращенном поднятой функцией. Разумеется, применяя StateT к разным монадам, получим разную семантику функции lift.

Благодарности[править]

Этот модуль использует ряд отрывков из All About Monads, с разрешения автора Jeff Newbern.

Примечания[править]

  1. В версии пакета mtl ранее 2.0.0.0, так и было построено. В настоящее время, однако, State s реализована как синоним типа для StateT s Identity.


Шаблон:Haskell/NotesSection

Шаблон:Haskell navigation