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 = ...


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

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

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:

These are both likely to be quite substantial exercises!