Functions of possibly cyclic data structures

Question

If I have a recursive ADT

data MyType = A | B | C MyType | D MyType MyType

I could write a function to determine whether an instance of MyType contains an A like so:

hasA :: MyType -> Bool
hasA A = True
hasA B = False
hasA (C x) = hasA x
hasA (D x y) = (hasA x) || (hasA y)

This would work for acyclic instances, but it does not halt for cyclic structures, e.g.

let x = C x in hasA x

Instead, in this example it should return False. In other cases (making use of D) it would erroneously not halt instead of returning True.

So, the question is how do I most easily write functions like hasA that work on cyclic structures? Racket has a particularly nice feature for this in the form of define/fix, that allows you to make a function like hasA behave as intended and return False 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?

Edit: I have now found that define/fix is in fact a macro created by Matt Might 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?

Answer 1

The key words to search for on Hackage are observable sharing. The data-reify package in those results looks especially relevant:

data-reify provided [sic] the ability to turn recursive structures into explicit graphs. Many (implicitly or explicitly) recursive data structure can be given this ability, via a type class instance. This gives an alternative to using Ref for observable sharing.