How can I do things like Clojure when using immutable collections in Objective-C?

Question

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.

Answer 1

Please see this article at Ridiculous Fish (written, I believe, by Cory Doras, an engineer on the AppKit team and also creator of the Fish shell):

Array: Our arrays, aren't. http://ridiculousfish.com/blog/posts/array.html

You've answered your question already:

Yes, you can do this now using the immutable NSArray and NSDictionary instances...

The beauty of the Cocoa framework is its simplicity, especially concerning data structures. The idea is that the behind-the-scenes code should determine how to implement the structure, not you. In practice, you only ever need two "types" of data structures: Arrays and Dictionaries (or Maps, if you've come from other languages). Of course, you need many "types" of implementations, but you only really need two ways of accessing your data; if you need more ways, then that's where custom classes and composition come into play.

As for your concern of efficiency: don't worry about it. The article by Cory (Ridiculous Fish) reveals that under-the-hood, Apple has already met your terms for efficiency. It is after all just pointers, as Ian Murray pointed out in the comments: everything is reference counted and only copied if necessary. It is most probable that when you "copy" or "mutableCopy" an NSArray or NSDictionary that the underlying data is not actually copied. To see how this could be implemented, see Rob Pike's article on the Go language here: http://blog.golang.org/slices. I'm almost certain that Cocoa follows a similar pattern, perhaps even to a further extent.

Additionally, with the advent of Objective-C "blocks," it is now more and more feasible to program in a functional style à la LISP variants (such as Clojure). In fact, I would highly recommend this and encourage you to continue on this path. It can lead to much stabler, cleaner code if done right.

Answer 2

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?.