Clojure, for example, has implementations for Sets, Maps, Vectors.
The advantage of a persistent data structure is that instead of destructively modifying a data structure, we create a new one via sharing, often in O(log n) time. Some people would argue that this makes code ‘more functional/pure’ and easier to debug.
The disadvantage of persistent data structures is that (1) in general, they have worse big-O constants and (2) O(1) ops often become O(log n) ops // generally via some ‘tree structure’ to enable sharing.
I am wondering if Kotlin itself (instead of external libraries) has plan to support persistent data structures for the commonly used structures (or if not, how it is against Kotlin philosophies ).
There is currently ongoing development of a library like that for kotlin:
This library might at some point be added to the stdlib as stated here. The question is what there is to gain by doing so. The philosophy as far as I know it, is not to reimplement functionality, that already exists in java, but to just add extensions to improve its usage from within kotlin. That being said some stuff is easier to just rewrite to match kotlin’s design philosophy instead of wrapping an existing java library. Truly immutable data might be one of those areas ( JetBrains at least thinks so).
I do not fully agree. I think in many cases 2 is a good option as well. You will just have to create interfaces/wrappers for the platform dependent code. This should also be easier once inline classes are fully supported feature: KEEP/inline-classes.md at 8e6737479e65d1b2828fda782eb7427c1e4b4456 · zarechenskiy/KEEP · GitHub
That does not mean that option 3 is not a valid option as well, but by going with option 2 the Kotlin team can focus on other problems right now. There is however a big problem with option 3. Either you have to implement each class differently for each target platform or you miss out on platform specific optimizations. That is another good reason for using native libraries, as they are mostly maintained by communities who know far more about their system than the kotlin community does, as Kotlin is mostly focused on Java.
I have never implemented a production compiler, never mind multiplatform production compilers – so my estimates here may be way off.
One very serious problem I see with #2 is as follows:
2a. on a single platform env, we can say: “JVM is truth – whatever the JVM does is the correct behaviour”
2b. if we are wrapping a JVM lib and a JS lib, it is very unlikely that they will have identical behaviour (and that over time, they continue to have identical behaviour), this seems to push us towards a situation where:
2ba. abstraction is leaky because it has different behaviour on JVM vs JS
2bb. lots of efforts are put into Kotlin wrapper code to get the two to behave identically (perhaps as much work as impl from scratch)
2c. I believe persistent/immutable algorithms are fairly well studied/understood, almost to the level of classical algorithms taught in University theory courses.
2d. I’m guessing that a nice persistent data structure library would be on the same level of work as the C++ STL. I do not want to underplay the amount of work it will take Jetbrains, but amortized over all IntelliJ/Kotlin users, it seems like a good deal.
