[Haskell-cafe] An issue with EDSLs in the ``finally tagless'' tradition

[wren ng thornton]

Brad Larsen wrote:
> The modularity problem I speak of is that to add a new interpretation of the
> DSL, I will likely have to modify the EDSL definition to add additional
> constraints.  Ideally, I would like to be able to define the EDSL once, in a
> module, and be able to write arbitrary interpretations of it in other
> modules, without having to go back and change the EDSL definition.

The canonical, if theoretically unsatisfying, way to do this is to lift 
all type variables into the class specification. Thus, instead of

     class Foo f where
         foo :: forall a. a -> f a

we would instead have

     class Foo f a where
         foo :: a -> f a

According to the intention of the design, variables thus lifted should 
remain polymorphic in instances however they can have contexts applied 
to them:

     instance (Num a) => Foo F a where
         foo = ...

The reason this is unsatisfying is that there's no way to enforce that 
instances don't ground these variables, which can interfere with the 
validity of applying certain laws/transformations. Also, if you need to 
lift more than one variable in the same class then it can be tricky to 
do the encoding right. For instance, when converting Monad into this 
form (e.g. so we can define an instance for Set) it is prudent to 
separate it into one class for return and another for join/(>>=)/(>>). 
But it does solve the problem at hand.

-- 
Live well,
~wren