Ответ 1
Существует ли канонический подход к подобным структурам данных? Возможно, обертка вокруг IO делает неизбежным небезопаснымPerformIO менее опасным "поиском", запрещая большинство операций ввода-вывода?
Да, точно. Вы только что придумали ST monad, представленный Launchbury и Peyton Jones около 20 лет назад.
Монашка ST допускает только эффекты памяти локальной области. Примечательно, что он использует систему типов, чтобы гарантировать, что побочные эффекты не видны за пределами области используемого им кодового блока.
Итак, до тех пор, пока вы используете память только через ссылки, только в локальной области, вы можете избежать unsafePerformIO и использовать вместо этого чистый ST, например, реализовать union-find.