the MPTC Dilemma (please solve)

[Roman Leshchinskiy]

On Thu, 23 Mar 2006, Claus Reinke wrote:

>>>               class Graph (g e v) where
>>>                   src :: e -> g e v -> v
>>>                   tgt :: e -> g e v -> v
>>> 
>>>               we associate edge and node types with a graph type by
>>>               making them parameters, and extract them by matching.
>> 
>> If I understand correctly, this requires all graphs to be polymorphic in 
>> the types of edges and vertices. Thus, you cannot (easily) define a graph 
>> which provides, say, only boolean edges. Moreover, doesn't this require 
>> higher-order matching?
>
> I've already answered the last question. as for polymorphism, all this
> requires is for a graph type parameterized by an edge and vertex
> type (just as the SML solution, which got full marks in this category,
> requires instantiations of the edge and vertex types in the graph structure).

Ah, I see. You are suggesting to introduce phantom type parameters to fake 
polymorphism for types which aren't really polymorphic. This might be 
acceptable as a temporary workaround but I don't think it is a good 
long-term solution. The ML implementation is not really comparable to this 
as instantiating structures is quite different from instantiating types.

>>>               class Edge g e | g -> e
>>>               instance Edge (g e v) e
>>>               class Vertex g v | g -> v
>>>               instance Vertex (g e v) v
>>> 
>>>               class (Edge g e,Vertex g v) => Graph g where
>>>                   src :: e -> g -> v
>>>                   tgt :: e -> g -> v
>>> 
>>>               (this assumes scoped type variables; also, current GHC,
>>>                contrary to its documentation, does not permit entirely 
>>> FD-determined variables in superclass contexts)
>> 
>> This does not seem to be a real improvement to me and, in fact, seems quite 
>> counterintuitive.
>
> it is, however, probably as close as we can come within current Haskell,

In what sense is this current Haskell? For this to work, you need at the 
very least to

   a) allow FD-determined variables to appear only in the superclass
      contexts but not in the head of class declarations (not supported by
      GHC at the moment),
   b) rely on scoped type variables (in a way which GHC doesn't support at
      the moment) and
   c) provide a way to keep FD outputs abstract even when the inputs are
      known (not supported by GHC).

While a) and b) might be fairly minor changes to GHC, c) seems to be a 
major one. Even if all this is added, what you end up with is essentially 
a verbose and counterintuitive hack for something which should be easy to 
do. This is not meant as a criticism of your (very interesting, IMO) 
approach - I agree that this is probably the best you can do with FDs. 
It's just that FDs simply seem to be a less than optimal mechanism for 
this kind of programming.

Also, it might be worth pointing out that even if all of the above worked,
you still couldn't do

   data VertexPair g = VP (Vertex g) (Vertex g)
   fstVertex :: Graph g => VertexPair g -> Vertex g
   fstVertex (VP v1 v2) = v1

   type Vertices g = [Vertex g]

Roman