Representing cyclic data structures efficiently in Haskell

[Andrew J Bromage]

G'day all.

On Mon, Jul 07, 2003 at 04:04:17PM +0100, Sarah Thompson wrote:

> > 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.

I replied:

> The direct Haskell equivalent is to use Refs; either IORefs or
> STRefs.  (I'd personally use IORefs, but that's because I like
> having IO around.)  Dereferencing an IORef is a constant-time
> operation, just like chasing a pointer in C.

I forgot to give an example. :-)

Suppose you want some kind of electronic circuit, as you suggested.
Abstractly, you want something like this:

	data Node
	  = Node NodeState [Component]

	data Component
	  = Resistor ResistorCharacteristics Node Node
	  | Transistor TransistorCharacteristics Node Node Node
	  | {- etc -}

You can make this indirect in introducing refs:

	type NodeRef = IORef Node
	type ComponentRef = IORef Component

	data Node
	  = Node NodeState [ComponentRef]

	data Component
	  = Resistor ResistorCharacteristics NodeRef NodeRef
	  | Transistor TransistorCharacteristics NodeRef NodeRef NodeRef

The data structures are mutable:

	getNodeState :: NodeRef -> IO NodeState
	getNodeState node
	  = do	Node state _ <- readIORef node
		return state

	setNodeState :: NodeRef -> NodeState -> IO ()
	setNodeState node state
	  = do	modifyIORef (\Node _ cs -> Node state cs) node

and it's straightforward to construct an index into the middle
somewhere:

	type NamedNodeIndex = FiniteMap String NodeRef

Cheers,
Andrew Bromage