Support for Immutability

[philippefutureboy]

Hey Guillaume!

Thanks for this great piece of software, it's hard to come across something as complete and in-depth as the libraries you are building.

I would like to know if you would be interested to add support for immutability, à la Immutable-JS.

Let me know what you think!

Cheers ✨

[Yomguithereal]

Hello @philippefutureboy. Thanks for your interest in the library.

I would like to know if you would be interested to add support for immutability

What do you mean exactly? Something like immutable heaps or something like this? I am not sure immutability would suit every structure of this library. But for multimaps etc. or things like that, sure, why not. We could build it on top of immutable-js quite easily (although immutable structures usually require more methods to cope with immutability).

However, I think that if this is a path we follow, I'd prefer to do that in a separate package like mnemonist-immutable for instance.

[philippefutureboy]

I am interested in functional programming, and immutability is a great way to reduce impurities in the code. More specifically, fully persistent data structures eliminate the side effects and allow the functions to be mathematically provable.

I can see how BloomFilters, BitSets, SparseSets and other memory-optimized data structures might lose their purpose when changed to be immutable, but other than that I'd go to argue that most, if not all data structures could benefit from immutability. I would have to look more into the implementation of the DynamicArray to see how it would affect performance.

In order, I would argue that the data structures that would benefit the most from immutability would be the Graph (graphology), Linked List, Queue, Heap, and Map.

Then again, my theoretical knowledge of data structures is minimal.

As for moving to mnemonist-immutable, I am not sure if this is a good idea, mainly because that will mean that any changes done on mnemonist will have to be duplicated to mnemonist-immutable, thus increasing maintenance burden. Moreover, you will split your user base in two, potentially splitting the open source contribution efforts in two (not that important now since you are the only contributor, but who knows what the future reserves 🔮 ). If you absolutely want to keep your current data structures exempt of immutability, I would suggest to make extra constructors that start with Immutable like you did for your typed constructors in graphology.

So what do you think?

[Yomguithereal]

I would have to look more into the implementation of the DynamicArray to see how it would affect performance.

Why would you want an immutable DynamicArray? This would defeat its purpose. Just copying the content into another byte array each time would be needed and this would be very costly. Wouldn't the immutable-js List already fitting the use case with a more performant implementation? (Or are you needing an immutable byte array ?)

In order, I would argue that the data structures that would benefit the most from immutability would be the Graph (graphology), Linked List, Queue, Heap, and Map.

I agree. An immutable Graph is planned and some things to handle are listed here.

If you absolutely want to keep your current data structures exempt of immutability.

I absolutely do :). I use the library's structures for performance usually (except for the utility ones such as the *Map etc.)

The thing I also want to avoid is to oblige the user to load, say, immutable-js when they only want to load a standard mutable Heap, for instance. So I need to split the files anyway.

[philippefutureboy]

Why would you want an immutable DynamicArray? This would defeat its purpose. Just copying the content into another byte array each time would be needed and this would be very costly. Wouldn't the immutable-js List already fitting the use case with a more performant implementation? (Or are you needing an immutable byte array ?)

Well not exactly per say - Immutable data structures are built on top of Tries, so essentially any modification would be in O(1). Granted it would take more space than a dynamic TypedArray due to the structure on which the Trie is built, but computationally wise it would be just as efficient. Due to the memory oriented nature of the optimization I can get that having an object container for every element would defeat the purpose.

Since you aim at raw, native performance as much as possible I can now understand why immutability might get in the way. For every 1 operation originally required, you could end up with up to 10 operations necessary for immutability.

If we open a mnemonist-immutable repository, how do you see the future of features development?

[Yomguithereal]

If we open a mnemonist-immutable repository, how do you see the future of features development?

I would probably begin with utility classes such as the *Map etc. that can be easily implemented by relying on fb's immutable rather than having to implement my own HAMTs or other persistent data structures.

I would also add structure on-demand rather than developing them spontaneously I guess because they don't fit my current use-cases right now.

[philippefutureboy]

Sounds pretty good! When do we get started? :)

[Yomguithereal]

Do you need a precise structure in your use cases?

[philippefutureboy]

I expect Graph, Heap/Queue, and Trie to be the ones I will need the soonest.