Representing cyclic data structures efficiently in Haskell

[Andrew J Bromage]

G'day all.

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

> I'd considered something like embedding the type in the IO monad, with 
> links between components implemented as IORefs, but I'd really prefer 
> something cleaner (pure functional). If the code ends up horribly 
> complicated in order to get decent performance, I might as well fold and 
> use C++ instead.

At the risk of stating the obvious, IORefs _are_ pure functional. :-)

> I'm currently wondering about going for an adjacency list approach (as
> used by most graph libraries), with the tuples in the adjacency list
> extended to include input/output labels, resulting in a 4-ary tuple
> rather than the usual 2-ary. But, I don't want to be stuck with
> representing this as a list -- I really need log N lookups or
> performance will stink horribly as circuits get big. Maybe a pair of
> finite maps, allowing the edges to be traversed in either direction?

You could do that.  Or you could use just one FiniteMap and reverse
the iterator before you use it.  (Remember that reverse is an amortised
O(1) operation, assuming you need to traverse the whole list.)

Or you could take a copy of the FiniteMap source code and add your own
reverse iterator to complement the forward iterator which is already 
there.  You could even submit a patch. :-)

Or you could use a different data structure, say, one with O(n)
iteration from either end, O(log n) search and O(1) insertion onto
either end.  There are several of these floating around.  This one
is quite good:

	http://citeseer.nj.nec.com/25942.html

Cheers,
Andrew Bromage