«29.04.2015 Денис Николаевич Москвин Ещё о монадах План лекции Моноиды, Alternative, MonadPlus Мультипараметрические классы типов Монады с ...»
Функциональное программирование
Лекция 11. Трансформеры монад
Денис Николаевич Москвин
СПбАУ РАН, CSC
29.04.2015
Денис Николаевич Москвин Ещё о монадах
План лекции
Моноиды, Alternative, MonadPlus
Мультипараметрические классы типов
Монады с обработкой ошибок
Трансформеры монад
Денис Николаевич Москвин Ещё о монадах
План лекции
Моноиды, Alternative, MonadPlus
Мультипараметрические классы типов
Монады с обработкой ошибок
Трансформеры монад
Денис Николаевич Москвин Ещё о монадах Вспомним класс типов Monoid class Monoid a where mempty :: a mappend :: a - a - a Некоторые аппликативные функторы и монады являются, помимо всего прочего, моноидами (списки, Maybe). Например, instance Monoid a = Monoid (Maybe a) where mempty = Nothing Nothing ‘mappend‘ m =m m ‘mappend‘ Nothing = m Just m1 ‘mappend‘ Just m2 = Just (m1 ‘mappend‘ m2) Денис Николаевич Москвин Ещё о монадах Другой представитель для Monoid Maybe Полезны и другие способы сделать Maybe моноидом, например instance Monoid (Maybe a) where mempty = Nothing Nothing ‘mappend‘ m = m m@(Just _) ‘mappend‘ _ = m Поскольку для нельзя объявить двух представителей для одного типа, в стандартной библиотеке используется упаковка newtype First a = First { getFirst :: Maybe a } В отличие от предыдущей реализации, параметризующий Maybe тип a совершенно не важен.
Денис Николаевич Москвин Ещё о монадах Класс Alternative class Applicative f = Alternative f where empty :: f a (|) :: f a - f a - f a
-- One or more.
some :: f a - f [a] some v = some_v where many_v = some_v | pure [] some_v = (:) $ v * many_v
-- Zero or more.
many :: f a - f [a] many v = many_v where many_v = some_v | pure [] some_v = (:) $ v * many_v infixl 3 | Денис Николаевич Москвин Ещё о монадах Представитель для Alternative Maybe instance Alternative Maybe where empty = Nothing Nothing | m = m m@(Just _) | _ = m Представитель Alternative для Maybe ведёт себя, как упаковка
First, возвращая первый не-Nothing в цепочке альтернатив:
Сессия GHCi *Fp11 Nothing | (Just 3) | (Just 5) | Nothing Just 3 Денис Николаевич Москвин Ещё о монадах Интерфейс для парсера Alternative Parsec Сессия GHCi import Text.Parsec let parser = string "ABC" | string "DEF" parseTest parser "ABC123" "ABC" parseTest parser "DEF123" "DEF" parseTest parser "GHI123"
parse error at (line 1, column 1):
unexpected "G" expecting "ABC" or "DEF"
Эти представители имеют функциональность, аналогичную Alternative.
Денис Николаевич Москвин Ещё о монадах Законы MonadPlus Помимо законов моноидальной структуры требуют выполнения Left Zero – Левый ноль
Left Catch law (return a) ‘mplus‘ b return a Выполнения аналогичных законов требуют для Alternative.
Денис Николаевич Москвин Ещё о монадах Использование MonadPlus
Рассмотрим линейную алгебру в Z2 data Vector = Vector Int Int data Matrix = Matrix Vector Vector Хотим реализовать умножение так, чтобы можно было
Обычная сигнатура умножения из Num слишком бедна для этого.
Денис Николаевич Москвин Ещё о монадах Мультипараметрические классы типов
К сожалению, такое решение слишком полиморфно:
Сессия GHCi *Fp11 let a = Matrix (Vector 1 2) (Vector 3 4) *Fp11 let i = Matrix (Vector 1 0) (Vector 0 1) *Fp11 a *** i No instance for (Mult Matrix Matrix c) arising from a use of ‘***’ The type variable ‘c’ is ambiguous *Fp11 (a *** i) :: Matrix Matrix (Vector 1 2) (Vector 3 4) Типовая переменная c в действительности не является свободной, но системе вывода типов нужна соответствующая подсказка.
Денис Николаевич Москвин Ещё о монадах Функциональные зависимости Можно задать функциональную зависимость, указав, что тип c уникальным образом определяется типами a и b
Теперь все работает Сессия GHCi *Fp11 let a = Matrix (Vector 1 2) (Vector 3 4) *Fp11 let i = Matrix (Vector 1 0) (Vector 0 1) *Fp11 a *** i Matrix (Vector 1 2) (Vector 3 4) Нужна прагма {-# LANGUAGE FunctionalDependencies #-}.
(/?) :: Double - Double - Either DivByError Double x /? 0 = throwError ErrZero x /? y = return $ x / y example0 :: Double - Double - Either DivByError String example0 x y = action ‘catchError‘ handler where action = do q - x /? y return $ show q handler = \err - return $ show err Сессия GHCi *Fp11 example0 5 2 Right "2.5" *Fp11 example0 5 0 Right "ErrZero" Денис Николаевич Москвин Ещё о монадах Более полиморфный пример Деление, совместимое с произвольным механизмом обработки ошибок. (Нужна прагма {-# LANGUAGE FlexibleContexts #-}.)
Теперь могли бы использовать не только Either, но не будем.
example1 :: Double - Double - Either DivByError String example1 x y = action ‘catchError‘ handler where action = do q - x ?/? y return $ show q handler = \err - return $ show err
Моноиды, Alternative, MonadPlus Мультипараметрические классы типов Монады с обработкой ошибок Трансформеры монад Денис Николаевич Москвин Ещё о монадах Трансформеры монад: знакомство
*Fp11 evalState stInteger 0 *Fp11 evalState stString "0" "01" Что делать если хотим в одном монадическом вычислении работать с обоими состояниями?
Денис Николаевич Москвин Ещё о монадах Monad transformers are like onions
*Fp11 runIdentity $ evalStateT (evalStateT stComb 0) "0" (1,"01") В качестве основы помимо Identity используют также IO со специализированной liftIO.
монадой, то есть её return и (=) должны удовлетворять законам монад.
Нужен lift :: m a - t m a, поднимающий значение из трансформируемой монады в трансформированную.
В библиотеке transformers функция lift всегда вызывается вручную, в mtl только для неоднозначных ситуаций.
1. У трансформера должен быть кайнд t: (* - *) - * - * Определяем наш конкретный трансформер MyMonadT для монады MyMonad newtype MyMonadT m a = MyMonadT { runMyMonadT :: m (MyMonad a) } Такое определение согласовано с механизмом вызова comp :: (MyMonadT Identity) a runIdentity (runMyMonadT comp) :: a
newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) } MaybeT :: m (Maybe a) - MaybeT m a runMaybeT :: MaybeT m a - m (Maybe a) instance MonadTrans MaybeT where lift :: m a - MaybeT m a lift = MaybeT. liftM Just
Пояснение работы lift при поднятии get из State:
*Fp11 :t get get :: MonadState s m = m s *Fp11 :t lift get lift get :: (MonadState a m, MonadTrans t) = t m a
newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) } instance (Monad m) = Monad (MaybeT m) where fail :: String - MaybeT m a fail _ = MaybeT $ return Nothing
*Fp11 runIdentity $ evalStateT (runMaybeT mbSt) 0 Nothing *Fp11 runIdentity $ evalStateT (runMaybeT mbSt) 2 Just 3 Если хотим guard $ a = 3 нужно сделать MaybeT m представителем MonadPlus
Для любой пары монад можно избавиться от подъёма стандартных операций вложенной монады.
Например, для монады State стандартный интерфейс упакован (в библиотеке mtl) в класс типов с фундепсами
*Fp11 runIdentity $ evalStateT (runMaybeT mbSt’’) 2 Just 3 Денис Николаевич Москвин Ещё о монадах Таблица стандартных трансформеров
Если нам нужна функциональность Error и State, то есть наша монада должна быть представителем MonadError и MonadState.
Должны ли мы применять трансформер StateT к монаде Error или трансформер ErrorT к монаде State?
Решение зависит от того, какой в точности семантики мы ожидаем от комбинированной монады.
Денис Николаевич Москвин Ещё о монадахЧто во что вкладывать?
Применение StateT к монаде Error даёт функцию трансформирования типа s - Either e (a, s).
Применение ErrorT к монаде State даёт функцию трансформирования типа s - (Either e a, s).
Порядок зависит от той роли, которую ошибка играет в вычислениях.
Если ошибка обозначает, что состояние не может быть вычислено, то нам следует применять StateT к Error.
Если ошибка обозначает, что значениене не может быть вычислено, но состояние при этом не портится, то нам следует применять ErrorT к State.