Representing cyclic data structures efficiently in Haskell

[Andrew J Bromage]

G'day all.

As you note, some kind of indirection is what you want here.

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.

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.

Cheers,
Andrew Bromage