In Haskell, how can I freeze/thaw a mutable vector of mutable vectors in O(1)?

user_7058336 0
Viewed 261

I'm using MVector's from the vector library to represent some adjacency list for a graph. This question requires good knowledge of the vector package.

I want some of my graph functions to take as input a mutable graph, because they might change it. And some other functions should take as input an immutable graph because they are not meant to change it.

Until now each graph function I have is taking a mutable graph as input. This is not nice.

I like how unsafeFreeze from here https://hackage.haskell.org/package/vector-0.12.1.2/docs/Data-Vector-Generic.html allows to get an immutable version of a vector in O(1). I believe that under the hood it really does nothing else than casting the type.

Essentially I want to be able to "unsafe" freeze frequently any complex mutable structure at zero cost, so that I can pass it to functions where an immutable argument is required. Just like in any common programming language. Despite the "unsafe" prefix, I feel this is not unsafe practice if the frozen structure is discarded right after its use as an immutable argument. Garbage collection should not happen as the mutable version is not discarded, and frozen version should point to the same memory representation as the mutable version.

What I'm having trouble with is freezing a graph seen as a mutable vector of mutable vectors. The only way I figured out so far, is to generate a new immutable version of the main vector with unsafeFreeze called on each mutable subvector. But that is O(n) in the length of the main vector. This is not acceptable.

To clarify, unsafe freezing the main vector alone, is not enough because it gets me a frozen vector of mutable vectors. In theory there should be a way to freeze everything at no cost, because internal memory representation should not change at all. It should be nothing but a cast.

Is there a way I can freeze a mutable vector of mutable vectors in (very cheap) O(1) ?

I am aware that this question is just very specialized on the vector package. IF you have alternative package suggestions for mutable vectors I'm happy to hear them.

Please don't answer "Use immutable structures. Period.". My opinion is that graphs, immutability, and performance, often don't go well together.

Thanks,

vector graph haskell
1 Answers

You can't. Sorry. Freezing is a one-array-at-a-time operation, period. What you might be able to do is build yourself an API that represents immutable structures using mutable structures. Depending on how you're using these, you may encounter some performance degradation in GC.

Another option is to use both unsafeFreeze and unsafeThaw. See for example the way HashMaps are constructed from lists in unorderedContainers. You have to be careful with this, because the type system won't be much help remembering what's going to be mutated and what won't be.

user_14776670
Related