Trying to compose non-composable: joint schemes

By Murat Kasimov
Nov. 2, 2019

Introduction

In this blog post I would like to show you an experimental method for dealing with multiple effects in Haskell that I have called joint schemes. What is the joint schema? It’s a schema that describes how some specific effect should be composed with other effects. I never seen something similar before, so I decided to dig into the capabilities of this approach.

In Haskell we get used to work with effects as functors, whose objects (arguments) are some expressions, which we are interested at some particular moment.

Definitions

Before we continue, let’s define some type annotations that will be used in this article, that will be very helpful when you’re starting thinking in terms of compositions over objects.

Let t be determined, some specific effect and let u be undetermined, just any other effect:

type (:=) t a = t a

If we have a simple one `Maybe` effect over some value it looks like:

Maybe := a

Composition of functors

type (:.) t u a = t (u a)

Let’s say, we want to add new List effect over existing one:

List :. Maybe := a

Natural transformation

type (~>) t u = forall a . t a -> u a

Function signature for safely accessing a list item would look like this:

List ~> Maybe

When we see type annotation like Maybe a, we abstract from existing of this a, focusing all our attention on this a like it always exists. The same story with List a - multiple a values, `State s a` - `a`, which depends from some current state, Either e a - some a that can throw an error `e`. For example: List :. Maybe := a - such expression is easy to imagine, this is a list of values, whose existing is unknown.

Compositions and transformers

In most real world programs we use many effects at the same time and the effect must then be composed in some way. There are mainly two different ways to do this: compositions and transformers. So, what are the pros and cons of these both methods?

Compositions:

  • There is no need in additional datatypes
  • There is no generalised method for merging effects
  • Everything is composable, as long as you don’t need monadic behaviour

Transformers:

  • They let you merge several effects into one
  • With lift you can do computations on any level of monad transformer stack
  • But it needs to have additional datatype (usually, newtype) (like ReaderT, StateT, ExceptT, MaybeT)
  • You cannot consider effects alone, but there are special functions for that (like mapReaderT, mapStateT, mapExceptT, mapMaybeT)

Transformers differ from compositions that they propagate effects on each other. For example, if you have an error on `Either`-level in StateT _ (Either _) a - all computation should stop. If you have just a composition State _ :. Either _ := a - in this case (just a functors composition) an error will not affect the whole computation.

Decomposing familiar effects

If we take a closer look on types for monad transformers from Kmett’s transformers library, we can see some patterns:

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) }

Transformers describe special case of how two effects - determined and undetermined should be composed. We will try to rewrite type definitions above in terms of determined and undetermined effects:

Reader: r -> u a ===> (->) r :. u := a ===> t :. u := a -- determined - t ~ (->) r, undetermined - u
Maybe: u (Maybe a) ===> u :. Maybe := a ===> u :. t := a -- determined - t ~ Maybe, undetermined - u
Either: u (Either e a) ===> u :. Either e := a ===> u :. t := a -- determined - t ~ Either e, undetermined - u

Some effects are pretty complicated and can be defined via composition of more simpler effects:

State: s -> m (a, s) ===> (->) s :. (,) s := a ==> t :. u :. t’ := a
newtype State s a = State ((->) s :. (,) s := a)

If we take a closer look again on first three examples, we can consider some patterns: in Reader, determined effect wraps undetermined one; but in the case of Either and Maybe we do the opposite thing - undetermined effects wrap determined. In case of State we put undetermined effect between two determined effects.

Fit familiar effects in joint schemes

Let’s try to express those patterns in types:

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)

We just defined joint schemes - they are functors compositions in wrappers, that can point on the positions of determined and undetermined effects. In the essence, methods of transformers, which names start with run unwrap these wrappers and return functors composition. We can generalise this operation:

class Composition t where
	type Primary t a :: *
	run :: t a -> Primary t a

Now we have a generalised way to run these schemes:

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

But what about transformers? We need to define new typeclass again. It consists of:

  • Some corresponding joint scheme that uniquely defined for this type
  • embed method to lift undetermined effect up to transformer layer
  • build method to make determined effect a transformer
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

All we need is to define instances, let’s start with Maybe and 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

We will create our own type for Reader because we don’t have it in base. And we need to define Composition instance for Reader just because it can be expressed via more simpler effect (a function arrow).

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

Let’s do the same with 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

Simple example

Let’s try our approach on the real world tasks - we’ll write a program that can test the correctness of location of various styles of brackets in a source code. First, we need to define types for brackets: they can be opened and closed; they can have different styles.

data Shape = Opened | Closed

data Style = Round | Square | Angle | Curly

Our program is indifferent to other symbols:

data Symbol = Nevermind | Bracket Style Shape

Also, we’re going to define what types of errors our program can stumble on:

data Stumble
	= Deadend (Int, Style) -- Closed bracket without opened one
	| Logjam (Int, Style)  -- Opened bracket without closed one
	| Mismatch (Int, Style) (Int, Style)  -- The closed bracket's style doesn't match to the opened one

What are the effects our program needs? We have to store a stack of styles of open brackets which should be checked later and we should stop all computation on first error. Let’s build a transformer:

State [(Int, Style)] :> Either Stumble := ()

This algorithm is easy: we traverse the structure of indexed brackets, if we haven’t stumbled on error and we have some brackets left in the stack - it means that the opened bracket doesn’t have the closed one.

checking :: Traversable t => t (Int, Symbol) -> Either Stumble ()
checking struct = run (traverse proceed struct) [] >>= \case
	(s : _, _) -> Left . Logjam $ s where
	([], _) -> Right ()

We put to the stack each opened bracket, and any closed one we match with the last opened one:

proceed :: (Int, Symbol) -> State [(Int, Style)] :> Either Stumble := ()
proceed (_, Nevermind) = pure ()
proceed (n, Bracket style Opened) = build . modify . (:) $ (n, style)
proceed (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

Conclusion

So, what do we have? According to this approach even very complicated effects can be decomposed on composition of simpler ones (that’s what for Composition typeclass) and we can inject any other effects into such schemes so they are working as transformers pretty well.

Suddenly, that trick doesn’t work with the mother of monads - continuations. Just because we cannot redefine it via functors composition.

I’ve created a tiny library with examples, if you have a bundle of effects in your pet-projects - you can try it. And if you have some troubles with it - email me. Also, there is full example code with brackets.