[Haskell-cafe] Detecting Cycles in Datastructures

[Paul Hudak]

Henning Thielemann wrote:
> On Fri, 18 Nov 2005, Paul Hudak wrote:
>> For example:
>>> fe1,fe2 :: Fix Expr
>>> fe1 e = Add (Const 1) (Const 1)  -- non-recursive
>>> fe2 e = Add (Const 1) e          -- recursive
> 
> Do you mean
> fe1 _ = Add (Const 1) Loop
> ?

No, I really meant it as written.  I included this example just to point 
out that an expression didn't have to be infinite to represent it as the 
fixpoint of a function.  Note that the least fixpoint of fe1 is "Add 
(Const 1) (Const 1)".

Loop shouldn't ever be used by the user -- that's why I added the 
comment that it was "not exported".  It's just there to "open" the 
function for inspection.  In this sense, the trick is analogous to the 
use of higher-order abstract syntax -- i.e. using the meta-language 
(Haskell) to represent functions in the object language (expressions).

   -Paul