haskelldata-structuresmonadsunion-findioref

Avoiding IORefs in pure code

I noticed that Data.UnionFind uses the IO monad to provide pointers via IORefs. I imagine everyone happily calls unsafePerformIO when using it locally in pure code, since the data structure is so well understood, but ..

Is there a canonical cleaner approach to such data structures? Perhaps a wrapper around IO that makes the inevitable unsafePerformIO less unsafe "looking" by prohibiting most IO operations?

Solution

  • Is there a canonical cleaner approach to such data structures? Perhaps a wrapper around IO that makes the inevitable unsafePerformIO less unsafe "looking" by prohibiting most IO operations?

    Yes, precisely. You have just invented the ST monad, introduced by Launchbury and Peyton Jones some 20 years ago.

    The ST monad allows only locally-scoped memory effects. It is remarkable in that it uses the type system to guarantee that side effects are not visible outside of the scope of the code block that is using them.

    So, as long as you use memory only via references, only in local scope, you can avoid unsafePerformIO and use pure ST instead, for example, to implement union-find.