[Haskell-cafe] Detecting Cycles in Datastructures

[Tom Hawkins]

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 
>> decent?
> 
> 
> No.

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?

Thanks!

-Tom

> 
>     -- Lennart
> 
>