Representing cyclic data structures efficiently in Haskell

Sarah Thompson
Mon, 07 Jul 2003 16:04:17 +0100

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      **** /
    / (_  _  _ _ |_   /                        * /
   /  __)(_|| (_|| ) /      * /
  / +               / /