Exercise: A Stream Processor Monad Transformer

The goal of this exercise is to derive an implementation of a monad transformer from an equational specification. The transformer we will develop adds a "stream processing" feature: actions in this monad can read elements from an input stream, write values to an output stream, and be composed by connecting two stream processors in series, so that the output stream of one becomes the input stream of the other.

The monad transformer type will be

newtype SP i o m a = ...

where

• i is the type of elements in the input stream,
• o is the type of elements in the output stream,
• m is the underlying monad, and
• a is the type of the value delivered by an action, as usual.

In addition to return, (>>=), and lift, the operations we will consider are

• put :: o -> SP i o m ()
• get :: SP i o m i
• (>>>) :: SP i c m z -> SP c o m a -> SP i o m a
• fail :: SP i o m a
• runSP :: SP i o m () -> m [o]

Stream processors can be thought of as a kind of process or coroutine, and it will be possible for them to deadlock: we use fail to represent a deadlocked action. We add equations for fail, which can be used to simplify deadlocked processes, and thereby simplify the kind of simplified terms we need. (The fail method is actually a method of the Monad class in Haskell, so we implement it in the Monad instance along with return and bind).

We do not supply a list of inputs to runSP, because it is easy to supply them in the monad using

puts xs = sequence (map put xs)
... runSP (puts inputs >>> m) ... 

We intend connection in series to be "lazy", in that f>>>g will run g as long as it requires no input, and run f only on demand to produce one of those inputs.

In addition to the usual monad and monad transformer laws, we assume

• fail >>= f = fail
• >>> is associative
• a>>>return x = return x
• a>>>(put x>>=f) = put x>>=(a>>>f())
• a>>>(lift m>>=f) = lift m>>= \x->a>>>f x
• a>>>fail = fail
• return x>>>(get>>=g) = fail
• (put x>>=f)>>>(get>>=g) = f ()>>>g x
• (lift m>>=f)>>>(get>>=g) = lift m>>= \x->f x>>>(get>>=g)
• (get>>=f)>>>(get>>=g) = get>>= \x->f x>>>(get>>=g)
• fail>>>(get>>=g) = fail
• run (return x) = return []
• run (lift m>>=f) = m >>= \x->run (f x)
• run (put x>>=f) = liftM (x:) (run (f ()))
• run (get>>=f) = return []
• run fail = return []

Part 1

Choose a suitable set of simplified terms, and derive an implementation based on it. Test your implementation in hugs. You will probably need to use an existential type somewhere to represent syntax involving the bind operator.

Part 2

Explore one of these possibilities:

• Derive a context-passing implementation of these operators. I found it helped to define put' x f = put x>>=f, get' f = get>>=f, lift' m f = lift m>>=f, and derive context passing implementations of the primed operators instead. The original operators can easily be defined in terms of them.
  As in the other examples we have seen, the associative law can be used to improve the performance of this implementation.

• Add a parallel composition operator to the algebra, postulate suitable laws, and derive an implementation for the simplified term case.

These are both likely to be quite substantial exercises!