Anonymous user
VList: Difference between revisions
m
{{out}} / -Category:Scala Implementations
(Added Scala) |
m ({{out}} / -Category:Scala Implementations) |
||
Line 3:
In computer science, the '''VList''' is a persistent data structure that combines the fast indexing of arrays with the easy extension of cons-based (or singly-linked) linked lists.
Like arrays, VLists have constant-time lookup on average and are highly compact, requiring only O(log ''n'') storage for pointers, allowing them to take advantage of locality of reference.
Like singly-linked or cons-based lists, they are persistent, and elements can be added to or removed from the front in constant time. Length can also be found in O(log ''n'') time.
The primary operations of a VList are:
Line 305 ⟶ 306:
}
</lang>
{{out}}
<pre>
zero value for type. empty vList:[]
Line 617 ⟶ 618:
v.printStructure()
}</lang>
{{out}}
<pre>
zero value for type. empty vList: []
Line 649 ⟶ 650:
=={{header|ooRexx}}==
The ooRexx queue class is a vlist implementation.
Here are some examples of usage:
<lang ooRexx>
-- show how to use the queue class
Line 672 ⟶ 674:
</lang>
{{out}}
<pre>
4
Line 779 ⟶ 781:
=={{header|Scala}}==
{{libheader|Scala}}
<blockquote cite="http://stackoverflow.com/questions/3107151/persistent-data-structures-in-scala">Two of Scala's 2.8 immutable data structures are vectors and hash tries, represented as 32-ary trees.
These were originally designed by '''Phil Bagwell''', who was working with my team at EPFL, then adopted for Clojure, and now finally adopted for Scala 2.8.
The Scala implementation shares a common root with the Clojure implementation, but is certainly not a port of it.</blockquote>
A quote of Martin Odersky, his co-worker Phil Bagwell† invented the VList.
<lang Scala>object VList extends App {
| |||