[Haskell-cafe] Detecting Cycles in Datastructures

[Lennart Augustsson]

Tom Hawkins wrote:
> 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?

No, what I'm reffering to is that the Haskell definitions says very,
very little about implementation details.  A valid Haskell
implementation might use some kind of call-by-name where each
use of a name expands to its definition.  Which in your case
would give an infinite tree for cyclic.

Since these kinds of things is actually up to the implementation
there is no way you can detect a cycle.  Because there might not
be one.

	-- Lennart