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 | hdaume@isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume
-----Original Message----- From: haskell-cafe-admin@haskell.org [mailto:haskell-cafe-admin@haskell.org] On Behalf Of Sarah Thompson Sent: Monday, July 07, 2003 8:04 AM To: haskell-cafe@haskell.org 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 **** / / (_ _ _ _ |_ / * / / __)(_|| (_|| ) / sarah@telergy.com * / / + / http://findatlantis.com/ / ----------------------------------------------
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe