Пытаясь композировать некомпозируемое: стыковочные схемы

    Введение


    В Haskell принято работать с эффектами как с функторами, объектами которых являются некоторые выражения, которые нам интересны в данный момент.

    Когда мы видим тип выражения Maybe a, мы абстрагируемся от фактического существования некоторого a, сконцентрировав все внимание именно на этом a. Та же история с List a — множественные значения a; State s aa, зависящая от некоторого текущего состояния; Either e aa, которое может вернуть некоторую ошибку 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 | Пример со скобками
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 0

    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

    Самое читаемое