[sfrank]

Sure you can do however, since Ruby allows destructive updates, why not use one of the established/traditional imperative data structures and then apply techniques to make them "persistent" (i.e. immutable in the functional programming sense as is also used by Okasaki and of course not using the trivial technique of copying the whole thing). Such techniques are e.g. presented in CLRS if I remember correctly.

It is not that Okasaki was the first one to implement any functional data structure. People have been doing this before and also in purely functional languages such as Haskell, ML, or Opal). He was the first to give a very nice overview, showed some new designs and even more important, showed a way for time complexity analysis (in a lazy evaluation context).

And it is this last part of the thesis that many people overlook: the importance of lazy evaluation (and thus the implied fundamental optimizations/evaluations performed by the compiler/runtime) for most of the presented data structures (i.e. everything with an amortized time complexity). Simply implementing Queues as presented in the thesis and not having a lazy language will lead to a very different time complexity than is proven there, because lazy semantics is vital for the given complexity analysis.

This is also the reason, why e.g. Clojure (or Opal from the early 90s, [1]) use other data structures to ensure functional (i.e. persistent) semantics in an eager/strict evaluation model.

[1] 1994, http://projects.uebb.tu-berlin.de/opal/trac/raw-attachment/w...