[Haskell-cafe] How to implement this? A case for scoped record labels?

wren ng thornton wren at freegeek.org
Tue May 26 18:09:01 EDT 2009

ntupel at googlemail.com wrote:
> wren ng thornton wrote:
> > A better approach would
> > probably be to use GADTs or the new data families which give a sort of dual
> > of typeclasses (typeclasses give a small set of functions for a large set of
> > types; GADTs give a large set of functions for a small set of types[0]).
> > Someone more familiar with those approaches should give those versions.
> Interesting, but I fail to see how this might be applied to the
> problem at hand. I played with associated types and they are quite
> neat. But I would still be working with type classes, so how would
> this be different from the first approach. W.r.t. GADTs I understood
> these as to provide a way to be more specific about the return type of
> constructor functions. But my problem is mostly a scope issue, isn't
> it?

I'm not familiar enough with the state of the art here to feel 
comfortable suggesting an implementation; hence leaving it to someone 
else. Technically GADTs are "just" for being more specific about the 
return types of constructor functions, but this is vastly more powerful 
than it may seem. For instance, GADTs can be combined with phantom types 
to great effect, e.g. for type checking dependent-like types.

GADTs can easily cover record selectors that apply to all constructors, 
and selectors that apply to one constructor (or a set of constructors 
producing the same type). If the family of selector sets forms a nice 
tree hierarchy, you can use phantom type constructors and type variables 
to express subtrees of that hierarchy as types, e.g.

     data Name m
     data Successful m
     data Bayeaux mesg where
         HandshakeRequest  :: ... -> Bayeaux (Name ...)
         HandshakeResponse :: ... -> Bayeaux (Name (Successful ...))

     name :: Bayeaux (Name m) -> String
     name (HandshakeRequest ...) = ...
     name (HandshakeResponse ...) = ...
     successful :: Bayeaux (Name (Successful m))
     name (HandshakeResponse ...) = ...

I don't know if the Bayeaux protocol is amenable to this or not. And I'm 
sure there's a prettier way to do it anyhow.

By using multiple phantom types you can encode any subset relation on 
selector sets that can be described by a tree-ordered space. If the 
subset relation is DAGy, then things get ugly again. You'll probably 
have to use typeclasses in some form or another eventually, the question 
is how much you rely on ad-hoc overloading vs how structured you can 
make things by using other techniques.

> I wonder if I am completely off here, but I am surprised that there is
> no progress on the scoped labels front. The Haskell wiki mentioned
> that the status quo is due to a missing optimum in the design space,
> but the same can be said about generic programming in Haskell and yet,
> GHC ships with Scrap your boilerplate. So we have to resort to type
> classes hacks instead of a proper solution. OTOH I might not have
> understood the relevance of GADTs for this problem and it is a
> non-issue but prima facie it doesn't seem to be.

The missing optimum is a big problem leading to the status quo. I think 
another issue is that noone is currently working on alternatives[1][2]. 
For SYB and the other generics stuff, people are actively working on it 
so there's more desire to make the options widely available, hoping that 
a clear winner will emerge.

Without active competition to weed out competitors, offering multiple 
options fragments the community. The monad transformer libraries seem to 
be in this quandary now. There was a lot of research a while back and 
there are lots of options out there, but people default to mtl for 
compatibility reasons and there hasn't been a strong campaign for one of 
the competitors to conquer mindshare and take over (though a small one 
is beginning now that the HP is here).

[1] I have a handful of ideas I've been kicking around, but I can't say 
that I've actually been "working" on any of them.

[2] If anyone *is* actively working in this area, I'd be curious to hear 
about it :)

Live well,

More information about the Haskell-Cafe mailing list