Representing cyclic data structures efficiently in Haskell

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

is broken, but the paper seems to be online at

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?-(