I've become somewhat addicted to using immutable collections (mainly in Clojure, which calls them "persistent data structures"), and would love to be able program this way in some contexts on iOS and OS X.
A key example of where this would be useful is to be able to "change" a dictionary by creating a modified copy, and have change listeners be able to query the difference between the old and new values, rather than try to codify the change as a property change event. Immutable data structures are also a game-changer for concurrent programming: no need for locks.
Yes, you can do this now using the immutable NSArray and NSDictionary instances, but it becomes increasingly inefficient to copy them to make "changed" versions as you have larger and larger collections and/or make changes frequently: a small change to a large data structure then involves a disproportionate amount of work.
I'm looking for a way to enable immutable data programming in Objective-C. To clarify what this might look like, and for some more of the advantages it offers, the research by Phil Bagwell referenced in this SO question is highly relevant.
I don't think there's a shortcut here.
Just as you imply, Clojure's persistent data structures are quite a different thing from the immutable collections classes that Cocoa provides.
If you want to use Clojure's persistent data structures from Obj-C, the only way to do so is to re-implement them in Objective-C. My understand is that many of these are described in Okasaki's book, Purely Functional Data Structures, and in the papers of Phil Bagwell.
This other answer has some links: What is the data structure behind Clojure's sets?.