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

[Frank Staals]

Roland Lutz <rlutz at hedmen.org> writes:

> Hi!
>
> I'm trying to implement a source-sink type of pattern where there are a number
> of sinks, each connected to exactly one source, and a number of sources, each
> connected to zero or more sinks.  The program consists of some modules, each
> defining their own sources and sinks. To illustrate this, here's what this
> would look like in C:


Hey Roland,

So essentially you want a data structure for some kind of bipartite
graph. 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 would give you something like:

import qualified Data.Map as M 

data MySource = MySource { sourceState :: String , % and any other data specific to sources }

data MySink = MySink { sinkState :: String, % and whatever else sinks have}

data BiGraph src snk = BiGraph { sourceToSinkMap :: M.Map src [snk]
                               , sinkToSourceMap :: M.Map snk src 
                               }

addEdge :: (src,snk) -> BiGraph src snk -> BiGraph src snk
addEdge (src,snk) (BiGraph m1 m2) = BiGraph (M.update src (snk :) m1)
                                            (M.insert snk src m2)
                                             % make sure to check that snk 
                                             % does not already occur in
                                             % m2 etc.


you essentially get your 'sinksForSource' functions for free:

sinksForSource :: src -> BiGraph src snk -> [snk]
sinksForSource src = M.lookup src . sourceToSinkMap 

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.

Note that instead of building such a graph type yourself you might also
just want to use some existing graph library out there (i.e. fgl or
so).

Hope this helps a bit. 

-- 

- Frank