Representing cyclic data structures efficiently in Haskell

C.Reinke C.Reinke@kent.ac.uk
Tue, 08 Jul 2003 13:12:01 +0100


> What is the best way to represent cyclic data structures in Haskell?

There used to be some work on direct cyclic representations at UCL:

  Dynamic Cyclic Data Structures in Lazy Functional Languages
  Chris Clack, Stuart Clayman, David Parrott
  Department of Computer Science, University College London,
  October 1995

The link to the project, from

  http://www.cs.ucl.ac.uk/staff/C.Clack/research/report94.html

is broken, but the paper seems to be online at

  http://www.cs.ucl.ac.uk/teaching/3C11/graph.ps

If you want to go for this direct cyclic representation, the
interplay with lazy memo functions is also interesting:

  J. Hughes, Lazy memo-functions, Functional Programming
  Languages and Computer Architecture, J-P. Jouannaud ed., 
  Springer Verlag, LNCS 201, 129-146, 1985. 

  (lazy memo-functions remember previous input-output pairs
   based only on pointer-info, which is sufficient to write
   functions over cyclic structures that, instead of infinitely
   unrolling the cycles, produce cyclic results)

  (not online?-(

Claus