[Haskell-cafe] Detecting Cycles in Datastructures
tom at confluent.org
Thu Oct 27 12:30:45 EDT 2005
Lennart Augustsson wrote:
> 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
Bummer -- but as I suspected.
> And there is nothing that says that your definition of cyclic
> will actually have a cycle in the implementation.
Would you elaborate? Are you referring to the possibility that
"cyclic", or at least the second Addition operand, may not be evaluated?
> -- Lennart
More information about the Haskell-Cafe