[Haskell-cafe] Detecting Cycles in Datastructures

[Nils Anders Danielsson]

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.

-- 
/NAD