«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.