[Haskell-cafe] How to implement a source-sink pattern
Frank Staals
frank at fstaals.net
Wed Apr 1 21:32:50 UTC 2015
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
More information about the Haskell-Cafe
mailing list