In Introduction to Constraint Programming I made something of a mistake. It was a remarkably easy one to make, because I stepped outside the bounds of the type system’s help – and especially that of those who’ve declared interfaces before me.

## Finding and Fixing the Mistake

The centrepiece of the article is an embedded language, which I’d initially written as just an applicative functor and quickly decided needed more power so I added a bind-like construct as well. The functor at its heart only operates on a subcategory of that of Haskell values – defined by a typeclass called `Embeddable`

:

class Embeddable a where subst :: Assignment -> a -> a instance Embeddable () where subst _ v = v instance Embeddable Term where subst = substTerm instance (Embeddable a, Embeddable b) => Embeddable (a -> b) where subst = const id

So we’ve got two ground types in the category – `()`

and `Term`

– and arbitrary-order functions on them. What we haven’t got is the target of the functor, `Embeddable a => Code a`

– which means that while the `Bind`

constructor types fine and so does its implementations, we can’t write the `join`

function that provides the difference between an applicative functor and a monad in Haskell. We can pass around higher-order Haskell functions, but our embedded language is strictly first-order!

Oops? We can fix this by adding a new instance:

instance Embeddable a => Embeddable (Code a) where subst _ c = c

What made this mistake easy to make, of course, was not having a `Monad`

-like typeclass with a defaulted join I was writing an instance for. That said, I did discover something new to me: I can have a "first-order-only monad" with the freedom of binding structure that comes with it. If I’m willing to invoke the relevant GHC flags, it can even play along with do notation.

## What Did We Have Before?

This new structure is interesting – `>>=`

still doesn’t admit self-analysis, but if I just want to know that there’s no passing around of computations happening in an EDSL then it’s a lot more pleasant to use than an `Arrow`

. The first piece of good news is that there’s already somewhere for it to fit in on HackageDB – the RMonad package. Of course, this implies that not every `RMonad`

is a monad.

For something with more theory developed, I believe it’s a Haskell encoding of a Relative Monad. A typeclass for them in Haskell using ConstraintKinds can be found in this draft paper: Subcategories in Haskell.