Presumably the only reason to choose unordered is a small performance improvement.

I make two claims:

1. The programmer + code reviewer cost of making a decision on each use far outweighs the benefit of that decision. You’re forced to make a choice 100% of the time but the decision is relevant 1% of the time.

2. In situations where the cost of retaining order is significant, it’s likely that another collection altogether is a better match. Rather than optimizing from ImmutableSet<Date> to ImmutableHashSet<Date>, programmers should probably skip right to Array<Long>.

Thanks for your consideration.

Hello! This library looks great but I'm interested in some targets that are currently not supported.
Missing targets that I'm interested in:

• watchosArm32
• watchosArm64
• watchosX86
• tvosArm64
• tvosX64
• linuxArm32Hfp
• linuxArm64

I got an error, maybe a compiler's one.

I am using Kotlin 1.3.41 and immutable 0.2, here the reproducer:

import kotlinx.collections.immutable.ImmutableCollection
import kotlinx.collections.immutable.ImmutableMap
import kotlinx.collections.immutable.ImmutableSet
import kotlinx.collections.immutable.persistentSetOf

fun main() {
    MyMap<Unit,Unit>().entries
}

class MyMap<K,V>: AbstractMap<K,V>(),ImmutableMap<K,V>{
    override val entries: ImmutableSet<Map.Entry<K, V>>
        get() = persistentSetOf()
    override val keys: ImmutableSet<K>
        get() = persistentSetOf()
    override val values: ImmutableCollection<V>
        get() = persistentSetOf()
}

Exception in thread "main" java.lang.AbstractMethodError: Receiver class MyMap does not define or inherit an implementation of the resolved method abstract getEntries()Ljava/util/Set; of abstract class kotlin.collections.AbstractMap.
	at kotlin.collections.AbstractMap.entrySet(AbstractMap.kt:21)
	at TestKt.main(Test.kt:7)
	at TestKt.main(Test.kt)

It would be great if this library could be used in common and javascript modules of multi-platform projects.

I tested the library with a simple TodoMVC/Redux/ImmutableJS-like exercice here

Here is my redux-like reducer

fun todoReducer(store: Store, event: Event): Store {
    val todos = when (event) {
        DeleteCompleted -> store.todos.mutate { list->
            list.removeIf(Todo::completed)
        }
        is AddTodo -> store.todos + Todo(event.id, event.text, false)
        is RemoveTodo -> {
            val todo = store.todo(event.id) ?: return store
            store.todos - todo
        }
        is ToggleCompletedTodo -> {
            val todo = store.todo(event.id) ?: return store
            store.todos.mutate { list ->
                list -= todo
                list += todo.copy(completed = !todo.completed)
            }
        }
        is EditTodo -> {
            val todo = store.todo(event.id) ?: return store
            store.todos.mutate { list ->
                list -= todo
                list += todo.copy(text = event.text)
            }
        }
    }
    return store.copy(todos = todos)
}

Had I use a List, I could have written

DeleteCompleted -> store.todos.filterNot(Todo::completed)

But that won't work because there is no overload of List.filter

DeleteCompleted -> store.todos.filterNot(Todo::completed).toImmutableList()

Not sure that this would be very efficient.

Without overloads of the stdlib extension functions, kotlinx.collections.immutable feels IMHO like a step backward

In addition to union operation, intersection, difference and inclusion can also be sped up quite a bit.
Inclusion (containsAll) is particularly important here because equals is implemented using it.

This is what I get when trying to run benchmarkNative from idea:

Execution failed for task ':benchmarks:nativeBenchmarkGenerate'.
> There was a failure while executing work items
   > A failure occurred while executing kotlinx.benchmark.gradle.NativeSourceGeneratorWorker
      > e: Failed to resolve Kotlin library: /home/belyaev/IdeaProjects/kotlinx.collections.immutable/benchmarks/build/classes/kotlin/native/main/benchmarks.klib

This is what I get when doing it from terminal:

./gradlew nativeBenchmark >native.out

FAILURE: Build failed with an exception.

* What went wrong:
Task 'nativeBenchmark' not found in root project 'Kotlin-Immutable-Collections'.

* Try:
Run gradlew tasks to get a list of available tasks. Run with --stacktrace option to get the stack trace. Run with --info or --debug option to get more log output. Run with --scan to get full insights.

* Get more help at https://help.gradle.org

BUILD FAILED in 889ms

Am I missing something here?

Is there a way to customize the collections to use referential equality that I'm not aware of, or is it not available yet?

Many thanks.

Hey I am curious,

I am surprised Google Guava got no mention in this library's README. What is the reasoning to have this library when Google Guava exists? Google Guava has an extensive set of collection types, including ImmutableMultiMap. Is this seeking to be a more lightweight library for just Immutable collections? Is it seeking to be more Kotlin-y?

Coming from Scala I would love to use this but it looks to be still in prototype phase and development has stopped? Is it production ready? What's the current plan with it?

Iterable.intersect(other: Iterable) takes a very long time to complete when called with a PersistentList as a parameter. Same function works faster with other iterables like List and Set. It is minutes with PersistentList and milliseconds with List.

I couldn't find the exact reason for that, but it seems that Collection.retainAll does something with the persistent list which takes ages to complete.

Here are some examples:

    (0..147853).toList().intersect((0..147853).toList()) // takes milliseconds
    (0..147853).toList().intersect((0..147853).toPersistentList()) // takes minutes
    (0..147853).toList().intersect((0..147853).toPersistentList().toSet()) // takes milliseconds

    (0..147853).toMutableList().retainAll((0..147853).toPersistentList()) // takes minutes
    (0..147853).toMutableList().retainAll((0..147853).toPersistentList().toList()) // takes milliseconds

I have nothing against using the PCollections library but the CHAMP algorithm is the current state of the art for JVM based immutable collection implementations:

https://blog.acolyer.org/2015/11/27/hamt/

You can find an implementation here:

https://github.com/usethesource/capsule

The footprint improvements are quite impressive. It'd be a shame if Kotlin shipped a library that wasn't using the current best research into the field, especially as an implementation already exists. It'd be a nice competitive advantage over other languages.

please add functions shown below:

/**
 * Returns an immutable list containing all elements of this collection.
 */
fun <T> Sequence<T>.toImmutableList(): ImmutableList<T> = toPersistentList()

/**
 * Returns a persistent list containing all elements of this collection.
 */
fun <T> Sequence<T>.toPersistentList(): PersistentList<T> = persistentListOf<T>() + this

/**
 * Returns an immutable set of all elements of this collection.
 */
fun <T> Sequence<T>.toImmutableSet(): ImmutableSet<T> = toPersistentSet()

/**
 * Returns a persistent set of all elements of this collection.
 */
fun <T> Sequence<T>.toPersistentSet(): PersistentSet<T> = persistentSetOf<T>() + this

Currently it delegates to addAll of the builder, which is inherited from the AbstractMutableCollections and adds elements one by one.

The other collection types are serializable as well, there is imho no reason why the immutable versions should not be.

It only happens in certain situations. It can be reproduced using following test:

class PersistentListTest {
    @Test
    fun `persistent list fails`() {
        var xs = persistentListOf(
            *(1..1885).map { it }.toTypedArray()
        )

        xs = xs.removeAll(
            (1..1837).map { it }
        )

        println(xs.size)

        xs.forEach {
            print(it)
        }
    }
}

print(it.i) fails with exception

java.lang.ClassCastException: class [Ljava.lang.Object; cannot be cast to class java.lang.Number
 ([Ljava.lang.Object; and java.lang.Number are in module java.base of loader 'bootstrap')

Calling replaceAll() on the mutable builder of a PersistentMap throws a ConcurrentModificationException.

Reproduction

To reproduce:

val pmap = persistentMapOf("a" to 1, "b" to 2)
val mmap = pmap.builder()
mmap.replaceAll { _, u -> u + 1 }	// throws ConcurrentModificationException
mmap.build()

What I expected

A persistent map with the mapping "a" to 2, "b" to 3.

What I got

An exception:

java.util.ConcurrentModificationException
	at kotlinx.collections.immutable.implementations.persistentOrderedMap.PersistentOrderedMapBuilderLinksIterator.checkForComodification(PersistentOrderedMapBuilderContentIterators.kt:57)
	at kotlinx.collections.immutable.implementations.persistentOrderedMap.PersistentOrderedMapBuilderLinksIterator.next(PersistentOrderedMapBuilderContentIterators.kt:26)
	at kotlinx.collections.immutable.implementations.persistentOrderedMap.PersistentOrderedMapBuilderEntriesIterator.next(PersistentOrderedMapBuilderContentIterators.kt:69)
	at kotlinx.collections.immutable.implementations.persistentOrderedMap.PersistentOrderedMapBuilderEntriesIterator.next(PersistentOrderedMapBuilderContentIterators.kt:61)
	at java.util.Map.replaceAll(Map.java:675)

Problem

Exception in thread "main" kotlin.KotlinNullPointerException
	at kotlinx.collections.immutable.implementations.persistentOrderedSet.PersistentOrderedSetIterator.next(PersistentOrderedSetIterator.kt:22)

When iterating over a PersistentOrderedSet

How to reproduce

After creating the PersistentSet alter a contained element so its hash code changes.

import kotlinx.collections.immutable.PersistentSet
import kotlinx.collections.immutable.toPersistentSet

fun main() {
    val changing = mutableSetOf("ok")
    val persistent: PersistentSet<Any> = setOf("constant", changing, "fix").toPersistentSet()
    doSomething(changing, persistent)
    changing.add("break iteration")
    doSomething(changing, persistent)
}

private fun doSomething(changing: MutableSet<String>, persistent: PersistentSet<Any>) {
    println("actual hash is ${changing.hashCode()}")
    val result = persistent.firstOrNull { it is Set<*> }
    println("Found $result")
}

Version used: 0.3.2

Details

The error occurs in TrieNode.get(Int, K, Int) because although the data is in the buffer hasEntryAt() returns false. Seems like the dataMap is outdated.

Note: The set is not changed during iteration but during two independent iterations.

I found no documentation on PersistentSet that values must not change their hash codes. Like a Set it should always be iterable.

In my actual project I used a data class with a collection. A workaround is to use a normal class with the default hashCode() implementation.

Current implementation inherited from AbstractMutableList results in O(NlogN) complexity of full iteration.

Following the README.md instructions and added below line to my gradle dependencies configuration:

implementation("org.jetbrains.kotlinx:kotlinx-collections-immutable-jvm:0.3")

I got the following error message from gradle:

> ./gradlew build
> Task :compileKotlin FAILED

FAILURE: Build failed with an exception.

* What went wrong:
Execution failed for task ':compileKotlin'.
> Could not resolve all files for configuration ':compileClasspath'.
   > Could not find org.jetbrains.kotlinx:kotlinx-collections-immutable-jvm:0.3.

And with the following link from jcenter, I got a 404 response: https://jcenter.bintray.com/org/jetbrains/kotlinx/kotlinx-collections-immutable-jvm/

However, if I follow the links and locate the jar on the jcenter web UI, I can download the jar successfully from this page: https://bintray.com/kotlin/kotlinx/kotlinx.collections.immutable/0.3#files/org%2Fjetbrains%2Fkotlinx%2Fkotlinx-collections-immutable-jvm%2F0.3

May I know whether version 0.3 is ready to be used?

There is some immediate backlash about immutable collections by Java users, as their understanding of the concept is either getting a full copy per operation, or receiving an exception on mutating methods.

The persistent keyword along with some references to Big O perf in the documentation may help spread the understanding of the difference.

Persistent ordered set can be implemented with a persistent hash set + some persistent list that keeps insertion order. Unfortunately the current persistent vector implementation doesn't suit well as such persistent list because of the slow deletion from the middle of list.

So the requirements for such list are:

• fast (<= logN) append to the end
• fast (<= logN) removal from the middle
• O(N) iteration in the order of insertion
• (nice to have) fast search of an element by some unique key (e.g. insertion counter)

You need to sign it at line 289

Copyright {yyyy} {name of copyright owner}

The concepts of being immutable and being mutable are mutually exclusive. The name of an immutable collection interface already states a contract. Extending an immutable interface by adding mutability methods breaks this contract. In addition, Barbara Liskov's substitution principle is broken: You cannot replace the base class with a derived class in all situations without damaging the expected behavior.

However, Kotlin has all it needs to clearly separate such interfaces and make them mutually incompatible:

`
class ImmutabilityContractViolationException : Exception()

interface IImmutable {
fun read(): Int
fun write(value: Int): Nothing = throw ImmutabilityContractViolationException()
}

interface IMutable {
fun read(): Int
fun write(value: Int) : Unit
}
`

The choice of internal representation for some PCollections scales on O(log2 n), where other implementations like Clojure's scale on O(log32 n)*

PCollections is a friendly implementation of persistent collections that's available today with little friction, but other options could be considered.

*Sources:

The Joy Of Clojure 2nd Ed Section 5.1.3

When learning about Clojure’s persistent data structures, you’re likely to hear the term O(log32 n) for those based on the persistent hash trie and O(log2 n) for the sorted structures. Accessing an element in a Clojure persistent structure by index is O(log n), or logarithmic.

https://github.com/GlenKPeterson/UncleJim/wiki/UncleJim%20vs.%20PCollections

After reading the other discussions about API design and backing implementation I decided to put some more work in to the tinkering I've been doing on persistent data structures. I think I now have enough done to start a discussion about the best approach.

https://github.com/amaranth/persistent-collections

There are interfaces for immutable collections, lists, sets, maps, sorted sets, and sorted maps. The implementation for lists is a bit-partitioned vector trie with O(log₃₂n) scaling. The hash map is sort of halfway between the standard clojure style HAMT and the CHAMP design, I use separate arrays for child nodes and data. The tree map is using an AA tree, which apparently Scala uses as well. The hash set and tree set are just wrappers around the map implementations. There is also a (most likely broken) finger tree implementation which I plan to try to use for a priority queue and possibly ordered sets and maps.

The performance of the library is... okay. I'm sure more optimization work can be done but my main goal was to get something that works first. On that note the unit tests could certainly use some work, right now they're mostly just ported from @andrewoma's dexx library (and I've just noticed the license gradle plugin wiped his name from the copyright headers, oops) but they at least show things aren't completely broken.

I'd love to see an API like this adopted, even if we decide to use UncleJim or dexx or pcollections for the backing implementation. The key design aspect mirrors the approach UncleJim uses in that the way to do mass updates to one of the collections in a performant way is to transform a Sequence and then turn that in to a new collection. This lets us avoid exposing the transient versions to the API which should remove any chance to misuse them and accidentally lose immutability.

As you can see, it is neither near library dependencies nor Gradle structure.

If we use version 0.2 instead of 0.3 then the jars appear, but the compiler still fails to pick anything from kotlinx namespace. As far as it is concerned, kotlinx. just doesn't exist.

I have no clue what is happening.

Our build.gradle.kts looks like:

import org.jetbrains.kotlin.gradle.plugin.mpp.KotlinNativeTarget

buildscript {
    repositories {
        mavenCentral()
    }

    dependencies {
        classpath(kotlin("gradle-plugin", version = "1.3.61"))
    }
}

repositories {
    mavenCentral()
    jcenter()
    maven(url = "https://kotlin.bintray.com/kotlinx")
}

plugins {
    kotlin("multiplatform") version "1.3.61"
}

kotlin {
    jvm()

    //select iOS target platform depending on the Xcode environment variables
    val iOSTarget: (String, KotlinNativeTarget.() -> Unit) -> KotlinNativeTarget =
        if (System.getenv("SDK_NAME")?.startsWith("iphoneos") == true)
            ::iosArm64
        else
            ::iosX64

    iOSTarget("ios") {
        binaries {
            framework {
                baseName = "zowo-shared"
            }
        }
    }

    sourceSets {
        all {
            languageSettings.apply {
                enableLanguageFeature("InlineClasses")
            }
        }

        val commonMain by getting {
            dependencies {
                implementation("org.jetbrains.kotlin:kotlin-stdlib-common")
                implementation("org.jetbrains.kotlinx:kotlinx-collections-immutable:0.3")
            }
        }

        val jvmMain by getting {
            dependencies {
                implementation("org.jetbrains.kotlin:kotlin-stdlib")
//                implementation("org.jetbrains.kotlinx:kotlinx-collections-immutable-jvm:0.2")
            }
        }

        val iosMain by getting {
        }
    }
}

val packForXcode by tasks.creating(Sync::class) {
    val targetDir = File(buildDir, "xcode-frameworks")

    /// selecting the right configuration for the iOS 
    /// framework depending on the environment
    /// variables set by Xcode build
    val mode = System.getenv("CONFIGURATION") ?: "DEBUG"
    val framework = kotlin.targets
                          .getByName<KotlinNativeTarget>("ios")
                          .binaries.getFramework(mode)
    inputs.property("mode", mode)
    dependsOn(framework.linkTask)

    from({ framework.outputDirectory })
    into(targetDir)

    /// generate a helpful ./gradlew wrapper with embedded Java path
    doLast {
        val gradlew = File(targetDir, "gradlew")
        gradlew.writeText("#!/bin/bash\n" 
            + "export 'JAVA_HOME=${System.getProperty("java.home")}'\n" 
            + "cd '${rootProject.rootDir}'\n" 
            + "./gradlew \$@\n")
        gradlew.setExecutable(true)
    }
}

tasks.getByName("build").dependsOn(packForXcode)

My main blocking issue is that https://github.com/Kotlin/kotlinx.serialization is not supported :(

Hi,
Why isn't this library published on jcenter?
Doing so would allow the methods count to appear here which can be important for Android apps nearing the dex size limit

Hallo everyone,
I have a question, which could probably be answered by @qurbonzoda

Are there any plans to implement a persistent LinkedHashMap? If yes, which complexity will put and remove functions have? O(n)?

Please close or delete the issue as soon as the question is answered. Thank you.

Let me also suggest my own FSet functional collections package as something you might want to look at: https://github.com/slburson/fset-java

The data structure it uses is an evolution of Stephen Adams' weight-balanced binary trees. The performance actually isn't bad, but there are newer and better choices and I'm not here to try to tell you you should use the FSet implementation.

What I would encourage you to do, though, is to have a look at the API. There may be some ideas in there you will find useful. The API was strongly influenced by a little-known proprietary language called Refine, which in turn was influenced by SETL.

In particular I would like to urge you not to name functional new-version operations the same as the corresponding mutating operation; so for instance, the operation that returns a set with a new element added should not be called add. Following SETL, I have called this operation with; plus is a reasonable choice as well. In general, I believe that functional operations should be named using nouns or prepositions, not verbs. Verbs suggest mutation. For instance, I recall reading once that users of Java's BigInteger would sometimes write x.add(y); and expect x to contain a different value afterwards; I think x.plus(y) is much more obviously an expression, not a statement.

(I suppose get on a map or list is an exception, though one could also make a case for at.)

immutable*Of(…) functions shouldn't be deprecated.

They should return Immutable* instead of Persistent*.

Currently, e.g.:

val x = immutableSetOf(1, 2, 3)
val y: ImmutableSet<Int> = immutableSetOf(1, 2, 3)

// x is PersistentSet<Int>
// y is ImmutableSet<Int>

x should be an ImmutableSet<Int>, but is a PersistentSet<Int>.

If I want an Immutable*, why force me to write an explicit type?

It's not like immutable*Of(…) functions are difficult to create or maintain…

I have the following problem in v0.3.2. If I create a list of 33 elements, convert it to PersistentList, and call removeAt for the last element, "assertion failed" will be thrown.

Code:

val list = List(33) { 0 }
val pList = list.toPersistentList()
pList.removeAt(pList.lastIndex)
/*
Assertion failed
        java.lang.AssertionError: Assertion failed
at kotlinx.collections.immutable.internal.CommonFunctionsKt.assert(commonFunctions.kt:8)
at kotlinx.collections.immutable.implementations.immutableList.SmallPersistentVector.<init>(SmallPersistentVector.kt:18)
at kotlinx.collections.immutable.implementations.immutableList.PersistentVector.pullLastBufferFromRoot(PersistentVector.kt:183)
at kotlinx.collections.immutable.implementations.immutableList.PersistentVector.removeFromTailAt(PersistentVector.kt:162)
at kotlinx.collections.immutable.implementations.immutableList.PersistentVector.removeAt(PersistentVector.kt:151)
[...]
*/

I discovered the problem when doing property-based tests for my code that used PersistentList. Here is an example of a property-based test that can find the problem above:

import kotlinx.collections.immutable.toPersistentList
import net.jqwik.api.AfterFailureMode
import net.jqwik.api.Arbitraries
import net.jqwik.api.Arbitrary
import net.jqwik.api.Combinators
import net.jqwik.api.ForAll
import net.jqwik.api.Property
import net.jqwik.api.Provide
import org.junit.Assert.assertEquals

/*

java.lang.AssertionError: Assertion failed

                              |-------------------jqwik-------------------
tries = 37404                 | # of calls to property
checks = 37404                | # of not rejected calls
generation = RANDOMIZED       | parameters are randomly generated
after-failure = RANDOM_SEED   | use a new random seed
edge-cases#mode = MIXIN       | edge cases are mixed in
edge-cases#total = 16         | # of all combined edge cases
edge-cases#tried = 16         | # of edge cases tried in current run
seed = -7880195249629813947   | random seed to reproduce generated values
sample = [RemoveCase(list=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], removeIndex=32)]
original-sample = [RemoveCase(list=[489591, 108, 333, 103363643, 5, 72, 16, 7, 109662, 1191, 74401, 1020547435, 4663656, 5, 2, 89, 17, 23, 17, 1948559812, 179, 1180415318, 141, 10, 69, 26, 44607, 11749, 3072, 46798, 511, 63050, 5201], removeIndex=32)]

Assertion failed
java.lang.AssertionError: Assertion failed
	at kotlinx.collections.immutable.internal.CommonFunctionsKt.assert(commonFunctions.kt:8)
	at kotlinx.collections.immutable.implementations.immutableList.SmallPersistentVector.<init>(SmallPersistentVector.kt:18)
	at kotlinx.collections.immutable.implementations.immutableList.PersistentVector.pullLastBufferFromRoot(PersistentVector.kt:183)
	at kotlinx.collections.immutable.implementations.immutableList.PersistentVector.removeFromTailAt(PersistentVector.kt:162)
	at kotlinx.collections.immutable.implementations.immutableList.PersistentVector.removeAt(PersistentVector.kt:151)
    [...]
    
 */
class PersistentListPropertyBasedTest {

    @Provide
    fun removeCases(): Arbitrary<RemoveCase> {
        val listArbitrary = generateNonNegativeIntegers().list().ofMinSize(1)
        val indexArbitrary = generateNonNegativeIntegers()
        return Combinators.combine(listArbitrary, indexArbitrary).`as` { list, index ->
            RemoveCase(list, index % list.size)
        }
    }

    @Property(tries = 50_000, afterFailure = AfterFailureMode.RANDOM_SEED)
    fun randomRemoves(@ForAll("removeCases") removeCase: RemoveCase) {
        val (list, removeIndex) = removeCase
        val persistentNewList = list.toPersistentList().removeAt(removeIndex)
        val mutableNewList = ArrayList(list).apply { removeAt(removeIndex) }
        assertEquals(mutableNewList, persistentNewList)
    }

    data class RemoveCase(
        val list: List<Int>,
        val removeIndex: Int
    )

    companion object {

        private fun generateNonNegativeIntegers() = Arbitraries.integers().between(0, Int.MAX_VALUE)

    }

}

There is already a PR in progress that should fix the problem (thanks!): #74

The current proposal document is undecided about whether to expose implementation types in the API. I'm confused about that. If only interface types are exposed, how can consumers be sure the collection objects they are dealing with are really immutable? Relying on adherence to the contract seems fragile. A buggy "smart" custom implementation can cause hard-to-diagnose problems far from the source of the error. It defeats the encapsulation benefits of using immutable types in APIs.

Description: An unexpected exception occurred when I tried to remove values form the a ImmutableMap, after a bit of testing I found that the error had nothing to do with my code, the following example show the minimal code required to cause the crash.

Code:

import kotlinx.collections.immutable.*

fun main(args: Array<String>) {
    val map = immutableMapOf(
            0 to "a",
            1 to "b",
            2 to "c"
    )

    val newMap = map - setOf(2)

    println(newMap)
}

Expected result: {0=a, 1=b}
Actual result:

Exception in thread "main" java.lang.IllegalStateException: Required value was null.

Rest of the stacktrace: https://pastebin.com/UCVMiZmC
Version used: 0.1

FEATURE REQUEST

A parameterless version of persistentHashMapOf() to avoid creating a useless builder and varargs parameter when the code is just going to create its own builder anyway.

fun <K, V> persistentHashMapOf(): PersistentMap<K, V> = PersistentHashMap.emptyOf<K,V>()

Parameter-less versions of persistentSetOf and persistentListOf() already exist. It seems odd that this is missing.

Names like add, remove and removeAll are, of course, appropriate names for corresponding operations.
But you should really, REALLY reconsider using these names. Each of your persistent collections is a far descendant of java.util.collections.Collection<E> and these names do override the respective methods in that interface with inappropriate result types, even though Kotlin does its magic to hide these behind the immutable kotlin.smth.Collection<E> interface.
This name clash may not be a problem now, but it already is the sole reason why your library does not compile with current Kotlin release (1.0.3) and does not work correctly with current Idea Plugin (see screenshot).
And with a small change to Kotlin ABI or a different JVM it may resurface when you least expect it.

From the readme:

Note: you need to import these operators from kotlinx.collections.immutable package in order for them to take the precedence over the ones from the standard library.

That makes it very easy to accidentally use the standard operators, which obviously has bad performance implications. Perhaps the operator functions should be instance methods so that the compiler prefers them over the standard plus/minus extension functions?

Current union (addAll) implementation for sets is O(logN * M) as far as I understand even when both sides have the same implementation.
It is certainly possible to improve that to log or even sub-log implementation for HAMTs by merging one-bit arrays only.
It is also possible to improve intersection, although atm you don't even have a method for intersection in the API.

Not sure if it helps maps in any way, but I guess it does.
While intersection is questionable, union is a very important and widely used operation (especially so when + is overloaded as union) for persistent sets and implementing this doesn't even need changing the api.

Programmers are lazy. Immutable collections are safer than mutable ones. Therefore, they should have shorter names (less typing) than the mutable ones.

To this end I'd like to propose using "im" instead of "immutable" as a prefix for persistent/immutable collections and builders. imListOf() instead of immutableListOf() makes it shorter than mutableListOf(). Still not as short as listOf().

I attended a Josh Bloch (I'll try to find the link later) where someone asked him about his biggest regret with the design of Java and he said it was that common collections weren't built into the language. When I look at JSON in JavaScript, or the built-in collection syntax in Clojure, it's really sweet. Arguably one of the stronger aspects of both languages that you can so briefly define data right in code. To that end, I designed all my builders to just be 3 letters: vec(), set(), map(), and tup() for Vector, HashSet, HashMap, and Tuple2/3.

Kotlin has already used [] as a shortcut for getElementAt(), so we aren't getting Clojure/JavaScript -like syntax for immutable lists, and we're pretty much out of other symbols. But I thought I'd throw it out there that really brief syntax for creating immutable data structures is awesome. Especially if it's shorter than the syntax for creating mutable ones. So whether you use "f" for frozen, "im" for immutable, or "p" for persistent, or something else, I just wanted to advocate for not having to type out the 9-letter word, "immutable" every time I reach for my preferred collections.

Still, we could follow Clojure's example of using # to prefix another symbol, so that #[1 2 3] could be a persistent/immutable list of ints. #<1 2 3> might be a set. #("one" 1) a tuple. #{#("one" 1) #("two" 2)} a map. It's a thought. I put a lot of data structures in my code for little immutable things. I don't like brevity in general, but for something like this, it's really sweet.

the name of the mutate extension could be a bit misleading, since it is returning a new collection with the given modification and not "mutate"ing the existing collection.

In this way, it is similar to the copy method on data classes, so maybe we could change mutate to be copy ?

or some other name that indicates that a new collection is being returned and the existing collection is unmodified.

All other toImmutable and toPersistent functions for immutable/persistent lists/sets take Iterable as their receiver, however toPersistentHashSet takes a Set.

toHashSet in the kotlin stdlib also takes Iterable.

This is inconvenient when converting from some other collection into a persistent hash set.

For example, here is a ConcurrentSet.

import kotlinx.collections.immutable.PersistentSet
import kotlinx.collections.immutable.persistentSetOf
import kotlinx.collections.immutable.toPersistentSet
import java.util.concurrent.atomic.AtomicReference

class ConcurrentSet<E>(initialValue: Set<E> = persistentSetOf()) : MutableSet<E> {
    private val set = AtomicReference(initialValue.toPersistentSet())
    
    fun get() = set.get()
    fun modify(operation: (PersistentSet<E>) -> PersistentSet<E>): Boolean {
        while (true) {
            val old = set.get()
            val new = operation(old)
            if (old === new) return false
            if (set.compareAndSet(old, new)) return true
        }
    }

    override fun iterator(): MutableIterator<E> = object : MutableIterator<E>, Iterator<E> by set.get().iterator() {
        override fun remove() = throw UnsupportedOperationException()
    }

    override fun add(element: E) = modify { it.add(element) }
    override fun addAll(elements: Collection<E>) = modify { it.addAll(elements) }
    override fun clear() {
        modify { persistentSetOf() }
    }
    override fun remove(element: E) = modify { it.remove(element) }
    override fun removeAll(elements: Collection<E>) = modify { it.removeAll(elements) }
    override fun retainAll(elements: Collection<E>): Boolean {
        TODO()
    }

    /**
     * Refrain from using these methods if concurrent safety is required.
     * Use get() instead.
     */
    override val size get() = set.get().size
    override fun contains(element: E) = set.get().contains(element)
    override fun containsAll(elements: Collection<E>) = set.get().containsAll(elements)
    override fun isEmpty() = set.get().isEmpty()
}

Tested with '0.3.2'

    @Test
    fun foo() {
        Array(33) { "" }
            .asList()
            .toPersistentList()
            .removeAt(32)
    }

Results in:

Assertion failed
java.lang.AssertionError: Assertion failed
	at kotlinx.collections.immutable.internal.CommonFunctionsKt.assert(commonFunctions.kt:8)
	at kotlinx.collections.immutable.implementations.immutableList.SmallPersistentVector.<init>(SmallPersistentVector.kt:18)
	at kotlinx.collections.immutable.implementations.immutableList.PersistentVector.pullLastBufferFromRoot(PersistentVector.kt:183)
	at kotlinx.collections.immutable.implementations.immutableList.PersistentVector.removeFromTailAt(PersistentVector.kt:162)
	at kotlinx.collections.immutable.implementations.immutableList.PersistentVector.removeAt(PersistentVector.kt:151)

e.g. For ImmutableLists, there's no implementation that I know of that supports random insertion of elements. By exposing such methods in builders it will lull users into believing the operations do not involve copying the entire list.

I'm not sure Builders are really required at all if the implementations are chosen carefully:

• Scala's Vector has efficient append/prepend
• Scala's Map/Set implementations also support efficient modifications

Example:

val map = persistentHashMapOf<IntWrapper, String>()
val iterator = map.put(IntWrapper(1, 1), "a").put(IntWrapper(2, 1), "b").iterator()

Canonicalization of collision nodes may help.

My library (https://github.com/andrewoma/dexx) is a largely port of Scala's collections.

It provides SortedMap/Set implementations as well as Vectors supporting 0(1) append/prepend that can be used as stack and queue implementations as well.