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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe