Roland Lutz
On Wed, 1 Apr 2015, Frank Staals wrote:
So essentially you want a data structure for some kind of bipartite graph.
Yes, with the additional constraint that the vertices in one partite set (the "sinks") each connect to exactly one edge.
The most haskelly way to do that would probably to define the graph to be simply define the Bipartite graph to be a pair of Maps, and define functions to add/delete nodes and edges to the graph that make sure that the two maps keep in sync.
This was actually my first approach, but I couldn't find appropriate key and value types to be stored in the map. Since the vertices are well-known global objects, it doesn't make much sense to store more than a handle here. But how do I connect the handle back to the data structure?
A vertex (source/sink) is not uniquely coupled with a graph; it may be in more than one graph. So, there is no easy way to define a function with type 'Vertex -> Graph'. In other words, you should pass around the graph data structure if you need connectivity information.
In this model you cannot direclty mix the sources and sinks from different modules. I.e. a 'BiGraph MySource MySink' cannot be used to also store a (MySecondSource,MySecondSink) pairs. If you do want that, you would need some wrapper type that distinguishes between the various 'MySink', 'MySecondSink', versions.
That's one of the points that trouble me. How would such a wrapper look like?
Assuming that the set of different sink types is fixed and known at compile time, simply: data Sink = SinkA ModuleA.Sink | SinkB ModuleB.Sink | ... If the sink types are not known then you need either Existential type or something like an open-union. An existentialtype will look something like: data Sink where Sink :: IsASink t => t -> Sink however, if you have a value of type Sink, you cannot recover what exact type of sink it was (i.e. if it was a ModuleA.Sink or a ModuleB.Sink): you only know that it has the properties specified by the IsASink typeclass. With open-unions you should be able to recover the exact type. However that is a bit more complicated. I don't have concrete experience with them myself, so others might be more helpful on that front.
I experimented a bit with your code (see below). I noticed that I have to specify "Ord src =>" and "Ord snk =>" in multiple places. Is there a way to state that type arguments for BiGraph always have to be instances of Ord?
Roland
Depends a bit, if you wish to keep the functions polymorphic in the source an sink types (src and snk) then you have to keep them. If you fill in the concrete types at hand, and you give them Ord instances, then (obviously) you don't have to keep the Ord constraints ;) Last note: If your source and sink types don't have a proper Ordering, you can switch to using (integer) explicit vertexIds and IntMaps. Similar to the API of fgl. However, in that case you have to do the bookkeeping of which vertex has which vertexId yourself.
updateEdge :: Ord src => Ord snk => (src, snk) -> BiGraph src snk -> BiGraph src snk updateEdge (src, snk) (BiGraph m1 m2) =
FWI: you would normally write multiple class constraints like (Ord src, Ord snk) =>, instead of Ord src => Ord snk =>. I'm kind of surprised the latter is still allowed. Regards, -- - Frank