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