Haskell: обработка циклических зависимостей при завязывании узла
При написании языка программирования, который будет иметь локальный вывод типов (т. Е. Он будет способен выводить типы за исключением параметров функций, таких как Scala), я столкнулся с проблемой циклических зависимостей.
Я выполняю проверку / вывод типов, рекурсивно исследуя AST и лениво отображая каждый необязательный типизированный узел в проверенный тип. Поскольку тип любого узла может зависеть от типов других узлов в AST, я связал узел так, чтобы я мог ссылаться на типы других узлов при выводе / проверке типа текущего узла (я сохраняю типизированный -AST в среде монады Reader).
Это прекрасно работает в типичном случае, но нарушает циклические зависимости, так как программа бесконечно следует за циклом в поисках известного типа.
Решение этой проблемы обычно (насколько я знаю) состоит в том, чтобы поддерживать коллекцию исследованных узлов, но я не могу придумать референтно-прозрачный способ сделать это, связывая узел, потому что я не знаю заранее порядок, в котором узлы будут посещаться / оцениваться, так как это зависит от графика их зависимости друг от друга.
Таким образом, кажется, мне нужно поддерживать локальную, изменчивую коллекцию исследованных узлов. Для этого я попробовал следующее:
- Использование монады State, которая завершилась неудачно, поскольку кажется, что каждое подвычисление получает свою собственную копию состояния, поэтому никакая информация об уже исследованных узлах не может быть разделена между различными ветвями вычисления.
- Использование монады IO с IORefs, что не позволило мне завязать узел из-за его строгости.
- С помощью
unsafePerformIOс IORefs, которые привели к проблемам с мутациями, происходящими не по порядку или вообще не возникающими. - Использование монады ST со STRefs, которая привнесла те же проблемы со строгостью, что и монада IO.
Наконец, я пришел к решению, использующему монаду ST, в которой я принудительно выполняю ленивую оценку при отображении AST, используя unsafeInterleaveST, который работает, но чувствует себя хрупким.
Есть ли более идиоматическое и / или ссылочно-прозрачное решение, которое не слишком длинное или сложное? Я бы включил пример кода, но моя самая простая формулировка этой проблемы ~250 строк.