Haskell: handling cyclic dependencies while tying the knot

Question

While writing a programming language that will feature local type inference (i.e. it will be capable of inferring types with the exception of function parameters, like Scala), I've run into a problem with cyclic dependencies.

I perform type-checking/inference by exploring the AST recursively, and lazily mapping each optionally-typed node to a type-checked node. Because the type of any node may depend on the types of other nodes within the AST, I've tied the knot so that I can refer to the types of other nodes while inferring/checking the type of the current node (I keep the typed-AST within the environment of a Reader monad).

This works perfectly well in the typical case, but breaks down with cyclic dependencies, as the program follows the loop endlessly in search of a known type.

The solution to this sort of problem generally (as far as I know) is to maintain a collection of explored nodes, but I cannot think of a referentially-transparent way of doing this while tying the knot, because I do not know in advance the order in which the nodes will be visited/evaluated, as this depends on the graph of their dependencies on one another.

As such, it seems I need to maintain a local, mutable collection of explored nodes. In order to do so, I tried the following:

• Using the State monad, which failed because it seems that each sub-computation receives its own copy of the state, so no information about already explored nodes can be shared between different branches of the computation.
• Using the IO monad with IORefs, which precluded me from tying the knot as a result of its strictness.
• Using unsafePerformIO with IORefs, which introduced problems with mutations occurring out of order or not at all.
• Using the ST monad with STRefs, which introduced the same problems with strictness as the IO monad.

Finally, I came up with a solution using the ST monad, in which I force lazy evaluation while mapping over the AST using unsafeInterleaveST, which works, but feels fragile.

Is there a more idiomatic and/or referentially transparent solution that isn't obscenely lengthy or complicated? I would have included a code sample, but my simplest formulation of this problem is ~250 lines.