listOf, setOf, and mapOf should return a persistent vector, persistent hash set, and persistent hash map, respectively.

In addition there should be a persistent linked list.

Scala does it like that, so does Clojure, which has adopted the concept from Scala.

Without persistent collections, entire immutable collections will be copied again and again for every additional value. This results in runtime complexity of O(n^2), as apposed to O(n).

(Per addition, O(n) instead of O(1))