[Haskell-cafe] writing graphs with do-notation

Emil Axelsson emax at chalmers.se
Mon Dec 14 01:48:24 EST 2009


This technique has been used to define netlists in hardware description 
languages. The original Lava [1] used a monad, but later switched to 
using observable sharing [2]. Wired [3] uses a monad similar to yours 
(but more complicated).

I think it would be nice to have a single library for defining such 
graphs (or maybe there is one already?). The graph structure in Wired 
could probably be divided into a purely structural part and a 
hardware-specific part.

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=
[2] http://www.cs.chalmers.se/~dave/papers/observable-sharing.pdf
[3] http://hackage.haskell.org/package/Wired

/ Emil

Soenke Hahn skrev:
> Hi!
> Some time ago, i needed to write down graphs in Haskell. I wanted to be able 
> to write them down without to much noise, to make them easily maintainable. I 
> came up with a way to define graphs using monads and the do notation. I thought 
> this might be interesting to someone, so i wrote a small script to illustrate 
> the idea. Here's an example:
> example :: Graph String
> example = buildGraph $ do
>     a <- mkNode "A" []
>     b <- mkNode "B" [a]
>     mkNode "C" [a, b]
> In this graph there are three nodes identified by ["A", "B", "C"] and three 
> edges ([("A", "B"), ("A", "C"), ("B", "C")]). Think of the variables a and b 
> as outputs of the nodes "A" and "B". Note that each node identifier needs to be 
> mentioned only once. Also the definition of edges (references to other nodes 
> via the outputs) can be checked at compile time.
> The attachment is a little script that defines a Graph-type (nothing 
> elaborate), the "buildGraph" function and an example graph that is a little 
> more complex than the above. The main function of the script prints the 
> example graph to stdout to be read by dot (or similar).
> By the way, it is possible to define cyclic graphs using mdo (RecursiveDo).
> I haven't come across something similar, so i thought, i'd share it. What do 
> you think?
> Sönke

More information about the Haskell-Cafe mailing list