On Thu, 27 Oct 2005, Lennart Augustsson
Tom Hawkins wrote:
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. And there is nothing that says that your definition of cyclic will actually have a cycle in the implementation.
On the other hand, other people have argued that "observable sharing" might be nice to have. See the following paper: Observable Sharing for Functional Circuit Description Koen Claessen, David Sands (Some version of it should be available online.) Adding observable sharing to Haskell would imply the loss of full beta equality. If I remember correctly the authors suggest that we only need the restricted form of beta equality where the argument is a defined value (for some notion of definedness). See the paper for their arguments. -- /NAD