One of my favourite things about the recursion schemes in Haskell are the generalised morphisms (gcata etc.) that allow interleaving (co-)monadic computations with recursion, using a monad transformer library. For example, as described in this great blog post.
However, I've run into a problem; to be able to use these functions we need the (co-)monads to be (co-)sequentiable. Consider a type signature for gana:
gana : Monad m => (forall z . m (f z) -> f (m z)) -> (a -> f (m a)) -> a -> b
The first argument essentially says that m must have a sequence operator.
Unfortunately, I've found that in practice, there are monads which are not distributive. For example:
- A monad representing a database transaction. When aborted, the transaction can be rolled back; if sequenced, it can only be rolled back to the point where it was sequenced.
- A concurrency monad, representing a lock on a resource, or an atomic computation. When sequenced, the lock is lost momentarily.
In this case, it is still possible to write a specialised recursion scheme that interleaves the monadic execution; but you lose the ability to fuse it using a monad transformer. i.e. if you want to combine such non-distributive monads, they can not be fused using a transformer with the monad/comonad in the f-(co)algebra. Concretely, I couldn't use a monad transformer to combine a DBTransaction monad with an apomorphism (ExceptT/EitherT); I'd need to write a custom recursion-scheme from scratch.
My question is whether anyone has suggestions for working around this limitation.