Введение
В Haskell принято работать с эффектами как с функторами, объектами которых являются некоторые выражения, которые нам интересны в данный момент.
Когда мы видим тип выражения Maybe a, мы абстрагируемся от фактического существования некоторого a, сконцентрировав все внимание именно на этом a. Та же история с List a — множественные значения a; State s a — a, зависящая от некоторого текущего состояния; Either e a — a, которое может вернуть некоторую ошибку e.
Перед тем как продолжить, в статье будут использоваться несколько определений:
type (:=) t a = t a -- | Объект функтора
type (:.) t u a = t (u a) -- | Композиция функторов
type (~>) t u = forall a . t a -> u a -- | Естественное преобразование
Например: List :. Maybe := a — такое выражение несложно представить, это список значений, существование которых находится под вопросом.
Далее, в качестве примера, будем использовать четыре распространенных типа: Reader, State, Either, Maybe.
Композиции и трансформеры
Самый очевидный способ наложить на выражение более одного эффекта — просто вложить один в другой, это обычная композиция функторов. В композициях, эффекты никак не влияют друг на друга (если не использовать над ними методы Traversable). А для того, чтобы слить множество эффектов в один, используются трансформеры. У каждого способа есть свои преимущества и недостатки:
Композиции:
- Не нужны дополнительные типы для их построения
- Нет общего метода для слияния эффектов с классами Functor/Applicative/Monad
- Все замечательно композируется, пока дело не доходит до монад
Трансформеры:
- Позволяют слить несколько эффектов в один
- Но нужен отдельный тип (чаще всего какой-нибудь newtype)
- С помощью lift можно выполнять вычисления на любом слое трансформеного стека
- Но нельзя учитывать эффекты по-отдельности, хотя есть специлизированные функции
Трансформеры отличаются от композиций наличия сцепления (не знаю, как это по-другому назвать). Имея некоторую композицию, можно превратить ее в трансформер и обратно. В этом нам помогут стыковочные схемы.
Стыковочные схемы
Если мы повнимательнее взглянем на типы для монадных трансформеров, то сможем выявить некоторые закономерности:
newtype ReaderT r m a = ReaderT { runReaderT :: r -> m a }
newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }
newtype ExceptT e m a = ExceptT { runExceptT :: m (Either e a)) }
newtype StateT s m a = StateT { runStateT :: s -> m (a,s) }
Трансформеры описывают частный случай того, как должны сцепляться текущий определенный и неопределенный эффект.
Пусть t — определенный, а u — неопределенный, пробуем:
Reader: r -> u a ===> (->) r :. u := a ===> t :. u := a -- t ~ (->) r
Maybe: u (Maybe a) ===> u :. Maybe := a ===> u :. t := a -- t ~ Maybe
Either: u (Either e a) ===> u :. Either e := a ===> u :. t := a -- t ~ Either e
Некоторые эффекты достаточно сложны и могут быть определены через композицию других, более простых эффектов:
State: s -> u (a, s) ===> (->) s :. (,) s := a ==> t :. u :. t’ := a -- t ~ (->) s, t' ~ (,) s
newtype State s a = State ((->) s :. (,) s := a)
Если мы посмотрим внимательнее на первые 3 примера, то сможем заметить общие паттерны: если в Reader, определенный эффект оборачивает неопределенный (берет в свои скобки, становится объектом функтора), то с Either и Maybe все наоборот — неопределенный эффект оборачивает определенный. В случае со State мы и вовсе помещаем функтор между двумя более простыми определенными эффектами.
Попробуем выразить эти паттерны в типах:
newtype TU t u a = TU (t :. u := a)
newtype UT t u a = UT (u :. t := a)
newtype TUT t u t' a = TUT (t :. u :. t' := a)
Мы только что определили стыковочные схемы — это композиция функторов в обертке, которая указывает позицию определенного и неопределенного эффекта.
По сути, методы для трансформеров, имена которых начинаются с run, просто снимают обертку трансформера, возращая композицию функторов. Опишем такой класс типов:
class Composition t where
type Primary t a :: *
run :: t a -> Primary t a
Теперь у нас есть универсальный способ запускать эти схемы:
instance Composition (TU t u) where
type Primary (TU t u) a = t :. u := a
run (TU x) = x
instance Composition (UT t u) where
type Primary (UT t u) a = u :. t := a
run (UT x) = x
instance Composition (TUT t u t') where
type Primary (TUT t u t') a = t :. u :. t' := a
run (TUT x) = x
А что насчет трансформеров? Тут тоже понадобится класс типов, в котором конкретному типу предписывается стыковочная схема, объявляется метод embed для поднятия неопределенного эффекта до уровня трансформера и build для конструирования определенного эффекта в трансформер:
class Composition t => Transformer t where
type Schema (t :: * -> *) (u :: * -> *) = (r :: * -> *) | r -> t u
embed :: Functor u => u ~> Schema t u
build :: Applicative u => t ~> Schema t u
type (:>) t u a = Transformer t => Schema t u a
Теперь осталось объявить экземпляры, начнем с Maybe и Either:
instance Transformer Maybe where
type Schema Maybe u = UT Maybe u
embed x = UT $ Just <$> x
build x = UT . pure $ x
instance Transformer (Either e) where
type Schema (Either e) u = UT (Either e) u
embed x = UT $ Right <$> x
build x = UT . pure $ x
Мы создадим свой тип для Reader, так как его нет в base. И ему так же нужен еще и экземлпяр класса Composition, так как он представляет из себя обертку для функтора стрелки:
newtype Reader e a = Reader (e -> a)
instance Composition (Reader e) where
type Primary (Reader e) a = (->) e a
run (Reader x) = x
instance Transformer (Reader e) where
type Schema (Reader e) u = TU ((->) e) u
embed x = TU . const $ x
build x = TU $ pure <$> run x
Проделываем нечто похожее со State:
newtype State s a = State ((->) s :. (,) s := a)
instance Composition (State s) where
type Primary (State s) a = (->) s :. (,) s := a
run (State x) = x
instance Transformer (State s) where
type Schema (State s) u = TUT ((->) s) u ((,) s)
embed x = TUT $ \s -> (s,) <$> x
build x = TUT $ pure <$> run x
В качестве примера
Остается протестировать это на задачах реального мира — в качестве примера напишем программу, рассчитывающую корректность расстановки различных типов скобок.
Определим типы для скобок: они могут быть открывающими и закрывающими; а также иметь различные стили:
data Shape = Opened | Closed
data Style = Round | Square | Angle | Curly
Нашей программы другие символы не интересны:
data Symbol = Nevermind | Bracket Style ShapeТак же определим перечень ошибок, с которыми может столкнуться наша программа:
data Stumble
= Deadend (Int, Style) -- Закрытая скобка без закрытой
| Logjam (Int, Style) -- Открытая скобка без закрытой
| Mismatch (Int, Style) (Int, Style) -- Стиль закрытой скобки не соответствует открытой
Какие эффекты нужны нашей программе? Нам нужно хранить список скобок, ожидающих проверки и нам нужно останавливаться при первой встречной ошибке. Составляем трансформер:
State [(Int, Style)] :> Either Stumble := ()Алгоритм прост: проходимся по структуре с индексированными скобками, если после прохода мы не натолкнулись на ошибку и у нас остались скобки в состоянии — значит у открытой скобки нет закрытой:
checking :: Traversable t => t (Int, Symbol) -> Either Stumble ()
checking struct = run (traverse proceed struct) [] >>= \case
(s : _, _) -> Left . Logjam $ s where
([], _) -> Right ()
Любую открытую скобку запоминаем, любую закрытую сравниваем с последней запомнившейся открытой:
proceed :: (Int, Symbol) -> State [(Int, Style)] :> Either Stumble := ()
proceed (_, Nevermind) = pure ()
proceed (n, Bracket style Opened) = build . modify . (:) $ (n, style)
procceed (n, Bracket closed Closed) = build get >>= \case
[]-> embed $ Left . Deadend $ (n, closed)
((m, opened) : ss) -> if closed /= opened
then embed . Left $ Mismatch (m, opened) (n, closed)
else build $ put ss where
Заключение
С помощью стыковочных схем, имея некоторую композицию функторов, мы можем превращать их в трансфомеры и обратно. К сожалению, такой трюк не сработет с матерью монад — продолжениями. А все потому что их нельзя представить как композию функторов, но можно как композицию профункторов… А впрочем, это совсем другая история.
Код библиотеки на Github | Документация на Hackage | Пример со скобками
