Representing cyclic data structures efficiently in Haskell

[Hal Daume]

>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 =3D 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=20
> [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
>=20
>=20
> What is the best way to represent cyclic data structures in Haskell?
>=20
> Lists are trivial. Trees are trivial. But what if the thing you're=20
> trying to represent is shaped like an electronic circuit, with a=20
> (possibly large) number of nodes connected by multiple arrows=20
> to other=20
> nodes? In an imperative language like C++, I'd probably just=20
> model the=20
> circuit directly, with objects representing nodes and pointers=20
> representing links between nodes. A good way to model this in=20
> Haskell is=20
> less obvious, however.
>=20
> A simplistic approach would be to represent such a structure=20
> as a list=20
> of nodes, where each node contained a list of other connected nodes.=20
> Containing the actual nodes within the sub-lists probably=20
> isn't feasible=20
> -- some kind of reference would be necessary in order to get around=20
> chicken-and-egg problems with instantiating the data=20
> structure. But, in=20
> this case, it's not so easy to see how one could 'walk' the structure=20
> efficiently, because moving from node to node would involve quite=20
> horrible (possibly slow) lookups. In C++, I'd simply follow a=20
> pointer,=20
> which would be an extremely fast operation.
>=20
> I would also need to implement efficient indexes into the=20
> data structure=20
> -- flat searching will be too slow for non-trivial amounts of=20
> data. In=20
> C++, I'd implement one or more external (probably STL-based) indexes=20
> that point into the main data structure.
>=20
> How do people typically solve this problem at the moment? I=20
> know a few=20
> people out there have written hardware compilers in Haskell=20
> and similar=20
> languages, so there should be some experience of this in the=20
> community.=20
> I can probably work something out soon enough, but=20
> reinventing the wheel=20
> is never a great idea.
>=20
> Thank you in advance,
>=20
> --=20
>       ----------------------------------------------
>      / __            + / Sarah Thompson      **** /
>     / (_  _  _ _ |_   /                        * /
>    /  __)(_|| (_|| ) / sarah@telergy.com      * /
>   / +               / http://findatlantis.com/ /
>  ----------------------------------------------
>=20
>=20
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>=20