[Haskell-cafe] Detecting Cycles in Datastructures

Nils Anders Danielsson nad at cs.chalmers.se
Thu Oct 27 15:34:17 EDT 2005

On Thu, 27 Oct 2005, Lennart Augustsson <lennart at augustsson.net> wrote:

> Tom Hawkins wrote:
>> Or phased differently, is it possible to make "Expr" an instance of
>> "Eq" such that cyclic == cyclic is smart enough to avoid a recursive
>> decent?
> No.  And there is nothing that says that your definition of cyclic
> will actually have a cycle in the implementation.

On the other hand, other people have argued that "observable sharing"
might be nice to have. See the following paper:

  Observable Sharing for Functional Circuit Description
  Koen Claessen, David Sands
  (Some version of it should be available online.)

Adding observable sharing to Haskell would imply the loss of full beta
equality. If I remember correctly the authors suggest that we only
need the restricted form of beta equality where the argument is a
defined value (for some notion of definedness). See the paper for
their arguments.


More information about the Haskell-Cafe mailing list