title: Functions of possibly cyclic data structures
body: <p>If I have a recursive ADT</p>
  
  <pre><code>data MyType = A | B | C MyType | D MyType MyType
  </code></pre>
  
  <p>I could write a function to determine whether an instance of <code>MyType</code> contains an <code>A</code> like so:</p>
  
  <pre><code>hasA :: MyType -&gt; Bool
  hasA A = True
  hasA B = False
  hasA (C x) = hasA x
  hasA (D x y) = (hasA x) || (hasA y)
  </code></pre>
  
  <p>This would work for acyclic instances, but it does not halt for cyclic structures, e.g.</p>
  
  <pre><code>let x = C x in hasA x
  </code></pre>
  
  <p>Instead, in this example it should return <code>False</code>. In other cases (making use of <code>D</code>) it would erroneously not halt instead of returning <code>True</code>.</p>
  
  <p>So, the question is how do I most easily write functions like <code>hasA</code> that work on cyclic structures? <a href="http://racket-lang.org/">Racket</a> has a particularly nice feature for this in the form of <code>define/fix</code>, that allows you to make a function like <code>hasA</code> behave as intended and return <code>False</code> for the structure in the example above, with hardly any extra code. Is there a way of doing something similar in Haskell? Is there an extension for it?</p>
  
  <p>Edit: I have now found that <code>define/fix</code> is in fact <a href="http://matt.might.net/articles/parsing-with-derivatives/code/dparse.rkt">a macro created by Matt Might</a> that takes advantage of Racket's meta-programming features, not a built-in feature, but this does not make it any less of a great feature of Racket. Maybe this macro could be reproduced in Haskell?</p>