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