Really Only Relative

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s