27 Oct
2005
27 Oct
'05
12:30 p.m.
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