Representing cyclic data structures efficiently in Haskell

[Antony Courtney]

Hi Sarah,

Representing cyclic structures is indeed somewhat tricky in a pure 
functional language.  The obvious representation (representing the link 
structure implicitly in an algebraic data type) doesn't work, because 
you can't obvserve cycles.

I recommend checking out two pieces of work in this area:

1.  Martin Erwig's work on inductive representations of graphs:

   Inductive Graphs and Functional Graph Algorithms, Martin Erwig
   Journal of Functional Programming Vol. 11, No. 5, 467-492, 2001

available from:

   http://cs.oregonstate.edu/~erwig/papers/abstracts.html#JFP01

2.  Koen Claessen and David Sands' work on observable sharing:

   Observable Sharing for Functional Circuit Description,
Koen Claessen, David Sands, published at ASIAN '99, in Phuket, Thailand

available from:

   http://www.math.chalmers.se/~koen/Papers/obs-shar.ps

Hope that helps,

	-Antony

-- 
Antony Courtney
Grad. Student, Dept. of Computer Science, Yale University
antony@apocalypse.org          http://www.apocalypse.org/pub/u/antony