[Haskell-cafe] How to implement a source-sink pattern

[Frank Staals]

Roland Lutz <rlutz at hedmen.org> writes:

> 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