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