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

Mario Blažević blamario at ciktel.net
Mon Apr 6 15:09:33 UTC 2015


On 04/01/2015 03:31 PM, Roland Lutz wrote:
> 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:
>
>
> /* global.h */
>
> struct source {
>     char *state;
>     /* some more fields */
> }
>
> struct sink {
>     struct source *source;
>     char *state;
>     /* some more fields */
> }
>
> struct sink **get_sinks_for_source(struct source *source);
>
> /* module_a.c */
>
> struct source a_source, another_source;
> struct sink foo, bar, baz;
>
> ...
>     foo.source = &a_source;
> ...
>

     One important thing you didn't state is: which parts of these data 
structures are immutable? The process of moving any data structure from 
C to Haskell depends on the answer, but otherwise can usually be done in 
a relatively mechanical fashion:

1. everything that is immutable should be shifted as deeply as possible, 
the mutable containers containing immutable ones;
2. map the data structures over: struct to a record, immutable array to 
an immutable array (or list or map or whatever, depending on the access 
pattern and performance requirements), mutable array to a mutable array;
3. map immutable non-null pointers to just the data structure they're 
pointing to, other immutable pointers to Maybe, mutable non-null 
pointers to STRef, other mutable pointers to STRef Maybe.
4. use runST to hide the whole mess behind a pure interface as much as 
possible.

     The result is unlikely to be optimal or elegant, but this process 
can get you a working implementation in Haskell. Once there, start 
refactoring the algorithms in and you'll likely be able to simplify both 
the data structure and the whole program. Take care to start with strong 
types and they will prevent you from doing anything stupid while 
refactoring.

     On a related note: I have no idea what Sink and Source are supposed 
to be for, but it's possible that pipes and conduits already provide it.



More information about the Haskell-Cafe mailing list