Representing cyclic data structures efficiently in Haskell

Antony Courtney
Mon, 07 Jul 2003 11:18:57 -0400

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:

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:

Hope that helps,


Antony Courtney
Grad. Student, Dept. of Computer Science, Yale University