Введение

В 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 | Пример со скобками