To answer the question in your subject, “Very Carefully.” While I don’t know much about your particular problem domain (and it seems others have given useful advice), I can say some general things about making mutable things immutable. There is a very simple way to make something mutable immutable: say that you won’t ever mutate it again! Doing this correctly is two-fold: you first have to know when you can do this and when it is useful (which requires in-depth understanding of the side-effects that the low-level API invokes), and second is knowing how to encapsulate your interface so that there is no type-checking use-case of your code (without unsafePerformIO) that accidentally mutates a pure structure. You can use this to do a standard pattern seen in ST and others: mutate during creation inside a monad, but when the monad is done running, return a pure version of the output with unsafePerformIO. If you can guarantee that another caching the pointer so that if someone else calls your function with the same arguments, you return the same pointer, is safe, then this is ok. Memcopying a datastructure when you need to modify it, while a cringe-worthy offense in your theoretical CS class, is a surprisingly practical and not-to-bad performing technique for making your data persistent. It works better the smaller the data structure is, and you'd be surprised how many C libraries implement some feature with a memory copy (moving GC, anyone?) Cheers, Edward