在编写具有本地类型推断功能的编程语言时（即，它能够推断除函数参数之外的类型，如 Scala），我遇到了循环依赖的问题。
我通过递归探索 AST 来执行类型检查/推理，并将每个可选类型节点延迟映射到类型检查节点。因为任何节点的类型可能取决于 AST 中其他节点的类型，所以我已经打好结这样我可以在推断/检查当前节点的类型时参考其他节点的类型（我保留键入的-AST 在 Reader monad 的环境中）。
这在典型情况下工作得很好，但会因循环依赖而崩溃，因为程序无休止地跟随循环寻找已知类型。
这类问题的解决方案一般（据我所知）是维护一个探索节点的集合，但我想不出在打结时这样做的参照透明方式，因为我事先不知道节点将被访问/评估的顺序，因为这取决于它们彼此之间的依赖关系图。
因此，我似乎需要维护一个本地的、可变的已探索节点集合。为此，我尝试了以下方法：
- 使用 State monad 失败了，因为似乎每个子计算都收到了自己的状态副本，因此无法在计算的不同分支之间共享有关已探索节点的信息。
- 将 IO monad 与 IORefs 一起使用，由于其严格性，这使我无法结缘。
- 与 IORefs 一起使用
unsafePerformIO，这引入了突变发生无序或根本不发生的问题。 - 将 ST monad 与 STRefs 一起使用，这引入了与 IO monad 相同的严格问题。
最后，我想出了一个使用 ST monad 的解决方案，在该解决方案中，我在使用 AST 映射时强制进行惰性求值unsafeInterleaveST，这可行，但感觉很脆弱。
是否有更惯用和/或引用透明的解决方案，不是冗长或复杂的？我会包含一个代码示例，但我对这个问题最简单的表述是大约 250 行。