[Haskell-cafe] writing graphs with do-notation
Levent Erkok
erkokl at gmail.com
Mon Dec 14 12:57:26 EST 2009
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=10.1.1.46.5221
> [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
More information about the Haskell-Cafe
mailing list