[Haskell-cafe] Detecting Cycles in Datastructures

Lennart Augustsson lennart at augustsson.net
Thu Oct 27 10:56:38 EDT 2005

Tom Hawkins wrote:
> In a pure language, is it possible to detect cycles in recursive data 
> structures?  For example, is it possible to determine that "cyclic" has 
> a loop? ...
> data Expr = Constant Int | Addition Expr Expr
> cyclic :: Expr
> cyclic = Addition (Constant 1) cyclic
> 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.

	-- Lennart

More information about the Haskell-Cafe mailing list