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