[Haskell-cafe] writing graphs with do-notation

Ivan Lazar Miljenovic ivan.miljenovic at gmail.com
Tue Dec 15 06:09:43 EST 2009

Emil Axelsson <emax at chalmers.se> writes:

> Yes, that's probably close to what I want. It would of course be nice
> to also have a monadic/applicative interface for building the
> graphs. In libraries like Wired where you're in a monad anyway, this
> would get rid of the need for IO.

IIRC, dotgen does this for Dot graphs for Graphviz.

> Koen Claessen has made a sketch of a generic graph library that we
> were planning to use as a basis for the EDSLs at Chalmers. But as far
> as I remember it looked a lot like the graph in data-reify, so maybe
> we should just use that instead.

Cale and I started on our own generic graph class... we should probably
get back to working on it...

> / Emil
> Levent Erkok skrev:
>> Andy Gill wrote a very nice recent paper on this topic which can
>> serve  as the basis for a generic implementation:
>>     http://www.ittc.ku.edu/~andygill/paper.php?label=DSLExtract09
>> As long as you do your "reification" in the IO monad, Andy's library
>> gives you the graph conversion for (almost-) free.
>> -Levent.
>> On Dec 13, 2009, at 10:48 PM, Emil Axelsson wrote:
>>> Hi!
>>> 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
>>> _______________________________________________
>>> Haskell-Cafe mailing list
>>> Haskell-Cafe at haskell.org
>>> http://www.haskell.org/mailman/listinfo/haskell-cafe
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

Ivan Lazar Miljenovic
Ivan.Miljenovic at gmail.com

More information about the Haskell-Cafe mailing list