[Haskell-cafe] writing graphs with do-notation
Emil Axelsson
emax at chalmers.se
Tue Dec 15 03:19:10 EST 2009
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.
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.
/ 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=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