Thanks for the explanation frank btw (did you dd it in the class comment because it would be gorgeous). I learned something today so I'm happy. Now what is the typical use case for such persistent structure? Stef On Feb 4, 2012, at 3:33 PM, Frank Shearar wrote:
On 3 February 2012 20:40, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
I wasn't sure what double-ended versus single-ended meant, and found some answer at the obvious place [1] which mentions Ada.Containers.Vectors is a dynamic array implementation which seems consistent with C++ [2]. While looking around I happened to bump into [3] which was too much for me but may be of interest to anyone playing with data structres. Skimming this shows it discussing efficiency of data structures in functional languages together with lazy variants of imperative language data structures. Would such apply to Smalltalk or is the object-oriented style of Smalltalk considered imperative rather than functional?
The standard tool set - OrderedCollection, Array, etc., are not functional at all - (myArray at: 1 put: 2) mutates myArray, - so I'd put them firmly on the "imperative" side of the fence.
There's nothing stopping one from writing functional data structures - Levente Uzonyi's written some persistent data structures, as have I. ("Persistent" means you get new versions of a data structure; if you hang onto those old versions you can roll back your changes.)
Can you explain a bit more Persistent?
Sure! A persistent data structure is an _apparently_ immutable data structure: editing the structure returns you a _new_ structure. If you can modify only the latest version of the structure, it's _partially_persistent_; if you can edit any version it is _fully_persistent_. Of course "edit" here means "get a new collection representing the edit"
For example, if you load the PersistentUnionFind package (no external dependencies) and print out this:
| p p1 p2 p3 | p := PersistentCollection initially: #(1 2 3). p1 := p at: 1 put: 4. p2 := p1 at: 2 put: 5. p3 := p at: 3 put: 0. {p. p1. p2. p3.} collect: #asArray
you get, with inline comments added:
#("p:" #(1 2 3) "p1:" #(4 2 3) "p2:" #(4 5 3) "p3:" #(1 2 0))
So you can see the different versions of the original array: p1 is p plus one replacement; p2 is p plus two replacements (or equivalently p1 plus one replacement).
You still get efficient access to the latest version, and the old versions describe themselves as a stack of undo operations - "I'm like the latest version, but with these changes".
So if you just print out p1, you'll see:
p1 printString. 'Ref(Diff(1, 4, Ref(Diff(3, 3, Ref(Arr(#(1 2 0)))))))'
The series of Diffs tell you how to get from the latest version - p3 - to the version of p1: "take p3 ( #(1 2 0) ), at index 3 put a 3, and at index 1 put a 1".
A Ref is a delegate: it allows your reference to something to stay the same even though the thing referenced changes.
Internally, as you access the latest version of the Collection the structure rewrites itself: if it's pointing to a Diff it "reroots" itself. (This does have the issue that if you hang onto two versions of the collection and access each version alternately, the PersistentCollection will waste a lot of time constantly rerooting itself.)
You can see then that keeping a reference to an old version allows you to undo arbitrary changes to the collection.
PersistentUnionFind _should_ load cleanly into Pharo: if it doesn't, let me know and I'll fix it so it does.
frank
Tx
http://www.squeaksource.com/Nutcracker/ is my own play area for these sorts of structures - PersistentUnionFind looks like a functional data structure while internally massively using side effects. http://www.lshift.net/blog/2011/12/31/translating-a-persistent-union-find-fr... has references to the original papers I used for my translation.
Okasaki's book is really good reading, if a bit advanced. It also has a bunch of stuff beyond just showing functional data structures. (Note that the red-black tree implementation is _incomplete_ - he leaves deleting nodes as an exercise for the reader. (See http://matt.might.net/articles/red-black-delete/))
frank
[1] http://en.wikipedia.org/wiki/Double-ended_queue [2] http://en.wikipedia.org/wiki/Sequence_container_%28C%2B%2B%29 [3] http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf