>From reading your message, it seems you want a graph library of sorts.
I've used FGL extensively and found it to be very nice. It even
provides both a purely functional interface as well as an
imperative-esque interface. It also comes with a bunch of standard
algorithms built in, though I don't know enough about circuitry stuff to
know whether those would be useful or not.
If FGL seems like overkill to you, I have my own little mini graph
library which basically looks like:
- An ADT, Node: newtype Node = Node Int deriving ...
- The 'Graph n e' data structure, containing:
- a FiniteMap from n -> Node
- an (growable?) array of type IOArray (Node,Node) e
the array represents the edges in the top half (i do some index fiddling
to get this efficient) and the finitemap represents the node labellings.
It's a pretty stupid interface and works a lot better when the graphs
are fixed size (that way you don't need to grow the array). But it
works.
--
Hal Daume III | [EMAIL PROTECTED]
"Arrest this man, he talks in maths." | www.isi.edu/~hdaume
> -----Original Message-----
> From: [EMAIL PROTECTED]
> [mailto:[EMAIL PROTECTED] On Behalf Of Sarah Thompson
> Sent: Monday, July 07, 2003 8:04 AM
> To: [EMAIL PROTECTED]
> Subject: Representing cyclic data structures efficiently in Haskell
>
>
> What is the best way to represent cyclic data structures in Haskell?
>
> Lists are trivial. Trees are trivial. But what if the thing you're
> trying to represent is shaped like an electronic circuit, with a
> (possibly large) number of nodes connected by multiple arrows
> to other
> nodes? In an imperative language like C++, I'd probably just
> model the
> circuit directly, with objects representing nodes and pointers
> representing links between nodes. A good way to model this in
> Haskell is
> less obvious, however.
>
> A simplistic approach would be to represent such a structure
> as a list
> of nodes, where each node contained a list of other connected nodes.
> Containing the actual nodes within the sub-lists probably
> isn't feasible
> -- some kind of reference would be necessary in order to get around
> chicken-and-egg problems with instantiating the data
> structure. But, in
> this case, it's not so easy to see how one could 'walk' the structure
> efficiently, because moving from node to node would involve quite
> horrible (possibly slow) lookups. In C++, I'd simply follow a
> pointer,
> which would be an extremely fast operation.
>
> I would also need to implement efficient indexes into the
> data structure
> -- flat searching will be too slow for non-trivial amounts of
> data. In
> C++, I'd implement one or more external (probably STL-based) indexes
> that point into the main data structure.
>
> How do people typically solve this problem at the moment? I
> know a few
> people out there have written hardware compilers in Haskell
> and similar
> languages, so there should be some experience of this in the
> community.
> I can probably work something out soon enough, but
> reinventing the wheel
> is never a great idea.
>
> Thank you in advance,
>
> --
> ----------------------------------------------
> / __ + / Sarah Thompson **** /
> / (_ _ _ _ |_ / * /
> / __)(_|| (_|| ) / [EMAIL PROTECTED] * /
> / + / http://findatlantis.com/ /
> ----------------------------------------------
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> [EMAIL PROTECTED]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
