VList

From Rosetta Code
VList is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Data Structure
This illustrates a data structure, a means of storing data within a program.

You may see other such structures in the Data Structures category.
This page uses content from Wikipedia. The original article was at VList. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

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:

  • Locate the kth element (O(1) average, O(log n) worst-case)
  • Add an element to the front of the VList (O(1) average, with an occasional allocation)
  • Obtain a new array beginning at the second element of an old array (O(1))
  • Compute the length of the list (O(log n))
Task

The task is to demonstrate creation of a VList and how to perform the primary operations.

C[edit]

#include <stdio.h>
#include <stdlib.h>
 
typedef struct sublist{
struct sublist* next;
int *buf;
} sublist_t;
 
sublist_t* sublist_new(size_t s)
{
sublist_t* sub = malloc(sizeof(sublist_t) + sizeof(int) * s);
sub->buf = (int*)(sub + 1);
sub->next = 0;
return sub;
}
 
typedef struct vlist_t {
sublist_t* head;
size_t last_size, ofs;
} vlist_t, *vlist;
 
vlist v_new()
{
vlist v = malloc(sizeof(vlist_t));
v->head = sublist_new(1);
v->last_size = 1;
v->ofs = 0;
return v;
}
 
void v_del(vlist v)
{
sublist_t *s;
while (v->head) {
s = v->head->next;
free(v->head);
v->head = s;
}
free(v);
}
 
inline size_t v_size(vlist v)
{
return v->last_size * 2 - v->ofs - 2;
}
 
int* v_addr(vlist v, size_t idx)
{
sublist_t *s = v->head;
size_t top = v->last_size, i = idx + v->ofs;
 
if (i + 2 >= (top << 1)) {
fprintf(stderr, "!: idx %d out of range\n", (int)idx);
abort();
}
while (s && i >= top) {
s = s->next, i ^= top;
top >>= 1;
}
return s->buf + i;
}
 
inline int v_elem(vlist v, size_t idx)
{
return *v_addr(v, idx);
}
 
int* v_unshift(vlist v, int x)
{
sublist_t* s;
int *p;
 
if (!v->ofs) {
if (!(s = sublist_new(v->last_size << 1))) {
fprintf(stderr, "?: alloc failure\n");
return 0;
}
v->ofs = (v->last_size <<= 1);
s->next = v->head;
v->head = s;
}
*(p = v->head->buf + --v->ofs) = x;
return p;
}
 
int v_shift(vlist v)
{
sublist_t* s;
int x;
 
if (v->last_size == 1 && v->ofs == 1) {
fprintf(stderr, "!: empty list\n");
abort();
}
x = v->head->buf[v->ofs++];
 
if (v->ofs == v->last_size) {
v->ofs = 0;
if (v->last_size > 1) {
s = v->head, v->head = s->next;
v->last_size >>= 1;
free(s);
}
}
return x;
}
 
int main()
{
int i;
 
vlist v = v_new();
for (i = 0; i < 10; i++) v_unshift(v, i);
 
printf("size: %d\n", v_size(v));
for (i = 0; i < 10; i++) printf("v[%d] = %d\n", i, v_elem(v, i));
for (i = 0; i < 10; i++) printf("shift: %d\n", v_shift(v));
 
/* v_shift(v); */ /* <- boom */
 
v_del(v);
return 0;
}

C++[edit]

Translation of: Go
 
#include <iostream>
#include <vector>
#include <forward_list>
#include <cassert>
#include <memory>
 
template<typename T>
class VList {
public:
VList() : datas(), offset(0) {}
private:
std::forward_list<std::shared_ptr<std::vector<T>>> datas;
int offset;
public:
 
// modify structure instead of returning a new one like the pure functional way does
void cons(const T& a) {
if(datas.empty()){
std::shared_ptr<std::vector<T>> base = std::shared_ptr<std::vector<T>>(new std::vector<T>(1)) ;
(*base)[0] = a;
datas.emplace_front(base);
offset = 0;
return;
}
if(offset == 0){
datas.front()->shrink_to_fit();
const int new_capacity = (int) datas.front()->capacity() * 2;
const int new_offset = new_capacity - 1;
std::shared_ptr<std::vector<T>> base = std::shared_ptr<std::vector<T>>(new std::vector<T>(new_capacity)) ;
(*base)[new_offset] = a;
datas.emplace_front(base);
offset = new_offset;
return ;
}
--offset;
(* datas.front())[offset] = a;
}
 
// lisp like cdr to keep previous version
VList* cdr() {
if (datas.empty()) {
// cdr of empty list is an empty list
return this;
}
VList* new_vlist = new VList();
new_vlist->datas = this->datas;
new_vlist->offset = offset;
new_vlist->offset++;
if(new_vlist->offset < new_vlist->datas.front()->capacity()){
return new_vlist;
}
new_vlist->offset = 0;
new_vlist->datas.front().reset();
new_vlist->datas.pop_front();
return new_vlist;
}
 
// compute the length of the list. (It's O(1).)
int length() {
if (datas.empty()) {
return 0;
}
return (int)datas.front()->capacity()*2 - this->offset - 1;
}
 
bool index(int i, T& out) {
bool isValid = false;
if (i >= 0) {
i += this->offset;
for(auto data : datas) {
if (i < data->size()) {
out = (* data)[i];
isValid = true;
break;
}
i -= data->size();
}
}
return isValid;
}
 
void printList() {
if (datas.empty()) {
std::cout << "[]" << std::endl;
return;
}
std::vector<T>* first = datas.front().get();
assert(NULL != first);
std::cout << "[";
for (int i=offset; i<first->size(); i++) {
std::cout << " " << (* first)[i];
}
for(auto data : datas) {
if(data.get() == datas.front().get())
continue;
for (int i=0; i<data->size(); i++) {
std::cout << " " << (* data)[i];
}
}
std::cout << " ]" << std::endl;
}
 
// One more method for demonstration purposes
void printStructure() {
std::cout << "offset:" << this->offset << std::endl;
if (datas.empty()) {
std::cout << "[]" << std::endl;
return ;
}
std::vector<T>* first = datas.front().get();
assert(NULL != first);
std::cout << "[";
for (int i=offset; i<first->size(); i++) {
std::cout << " " << (* first)[i];
}
std::cout << " ]" << std::endl;
for(auto data : datas) {
if(data.get() == datas.front().get())
continue;
std::cout << "[";
for (int i=0; i<data->size(); i++) {
std::cout << " " << (* data)[i];
}
std::cout << " ]" << std::endl;
}
std::cout << std::endl;
}
};
 
int main(int argc, const char * argv[]) {
 
std::unique_ptr<VList<char>> vlist = std::unique_ptr<VList<char>>(new VList<char>());
 
std::cout << "zero value for type. empty vList:";
vlist->printList();
vlist->printStructure();
 
std::cout << "demonstrate cons. 6 elements added:";
for (char a = '6'; a >= '1'; a--) {
vlist->cons(a);
}
vlist->printList();
vlist->printStructure();
 
std::cout << "demonstrate cdr. 1 element removed:";
vlist = std::unique_ptr<VList<char>>(vlist->cdr());
vlist->printList();
vlist->printStructure();
 
std::cout << "demonstrate length. length =" << vlist->length() << std::endl;
 
char out;
bool isValid = vlist->index(3, out);
if(isValid)
std::cout << "demonstrate element access. v[3] =" << out << std::endl;
 
std::cout << "show cdr releasing segment. 2 elements removed:";
vlist = std::unique_ptr<VList<char>>(vlist->cdr()->cdr());
vlist->printList();
vlist->printStructure();
 
return 0;
}
 
Output:
zero value for type.  empty vList:[]
offset:0
[]
demonstrate cons. 6 elements added:[ 1 2 3 4 5 6 ]
offset:1
[ 1 2 3 ]
[ 4 5 ]
[ 6 ]

demonstrate cdr. 1 element removed:[ 2 3 4 5 6 ]
offset:2
[ 2 3 ]
[ 4 5 ]
[ 6 ]

demonstrate length. length =5
demonstrate element access. v[3] =5
show cdr releasing segment. 2 elements removed:[ 4 5 6 ]
offset:0
[ 4 5 ]
[ 6 ]

D[edit]

Translation of: C
import core.stdc.stdio: fprintf, stderr;
import core.stdc.stdlib: malloc, free, abort;
 
/// Uses C malloc and free to manage its memory.
/// Use only VList.alloc and VList.free.
struct VList(T) {
static struct Sublist {
Sublist* next;
T[0] dataArr0;
 
@property data() inout pure nothrow {
return dataArr0.ptr;
}
 
static typeof(this)* alloc(in size_t len) nothrow {
auto ptr = cast(typeof(this)*)malloc(typeof(this).sizeof +
T.sizeof * len);
ptr.next = null;
return ptr;
}
}
 
// A dynamic array of pointers to growing buffers seems
// better than a linked list of them.
Sublist* head;
size_t lastSize, ofs;
 
static typeof(this)* alloc() nothrow {
auto v = cast(typeof(this)*)malloc(VList.sizeof);
enum startLength = 1;
v.head = Sublist.alloc(startLength);
v.lastSize = startLength;
v.ofs = 0;
return v;
}
 
void free() nothrow {
while (this.head) {
auto s = this.head.next;
.free(this.head);
this.head = s;
}
.free(&this);
}
 
@property size_t length() const nothrow {
return this.lastSize * 2 - this.ofs - 2;
}
 
T* addr(in size_t idx) const nothrow {
const(Sublist)* s = this.head;
size_t top = this.lastSize;
size_t i = idx + this.ofs;
 
if (i + 2 >= (top << 1)) {
fprintf(stderr, "!: idx %zd out of range\n", idx);
abort();
}
while (s && i >= top) {
s = s.next;
i ^= top;
top >>= 1;
}
return s.data + i;
}
 
T elem(in size_t idx) const nothrow {
return *this.addr(idx);
}
 
// Currently dangerous.
//T opIndex(in size_t idx) const nothrow {
// return elem(idx);
//}
 
T* prepend(in T x) nothrow {
if (!this.ofs) {
auto s = Sublist.alloc(this.lastSize << 1);
if (s == null) {
fprintf(stderr, "?: alloc failure\n");
return null;
}
this.lastSize <<= 1;
this.ofs = this.lastSize;
s.next = this.head;
this.head = s;
}
 
this.ofs--;
auto p = this.head.data + this.ofs;
*p = x;
return p;
}
 
T popHead() nothrow {
if (this.lastSize == 1 && this.ofs == 1) {
fprintf(stderr, "!: empty list\n");
abort();
}
 
auto x = this.head.data[this.ofs];
this.ofs++;
 
if (this.ofs == this.lastSize) {
this.ofs = 0;
if (this.lastSize > 1) {
auto s = this.head;
this.head = s.next;
this.lastSize >>= 1;
.free(s);
}
}
 
return x;
}
 
// Range protocol is missing.
}
 
 
void main() {
import std.stdio, std.bigint;
enum N = 10;
 
auto v = VList!BigInt.alloc;
foreach (immutable i; 0 .. N)
v.prepend(i.BigInt);
 
writefln("v.length = %d", v.length);
foreach (immutable i; 0 .. N)
writefln("v[%d] = %s", i, v.elem(i));
foreach (immutable i; 0 .. N)
writefln("popHead: %s", v.popHead);
 
v.free;
}
Output:
v.length = 10
v[0] = 9
v[1] = 8
v[2] = 7
v[3] = 6
v[4] = 5
v[5] = 4
v[6] = 3
v[7] = 2
v[8] = 1
v[9] = 0
popHead: 9
popHead: 8
popHead: 7
popHead: 6
popHead: 5
popHead: 4
popHead: 3
popHead: 2
popHead: 1
popHead: 0

Go[edit]

package main
 
import "fmt"
 
type vList struct {
base *vSeg
offset int
}
 
type vSeg struct {
next *vSeg
ele []vEle
}
 
// element type could be anything. i pick string to demonstrate the task.
type vEle string
 
// primary operation 1: locate the kth element.
func (v vList) index(i int) (r vEle) {
if i >= 0 {
i += v.offset
for sg := v.base; sg != nil; sg = sg.next {
if i < len(sg.ele) {
return sg.ele[i]
}
i -= len(sg.ele)
}
}
// consistent with the way Go panics on slice index out of range
panic("index out of range")
}
 
// primary operation 2: add an element to the front of the VList.
func (v vList) cons(a vEle) vList {
if v.base == nil {
return vList{base: &vSeg{ele: []vEle{a}}}
}
if v.offset == 0 {
l2 := len(v.base.ele) * 2
ele := make([]vEle, l2)
ele[l2-1] = a
return vList{&vSeg{v.base, ele}, l2 - 1}
}
v.offset--
v.base.ele[v.offset] = a
return v
}
 
// primary operation 3: obtain a new array beginning at the second element
// of an old array
func (v vList) cdr() vList {
if v.base == nil {
// consistent with panic above. (not consistent with lisp)
panic("cdr on empty vList")
}
v.offset++
if v.offset < len(v.base.ele) {
return v
}
return vList{v.base.next, 0}
}
 
// primary operation 4: compute the length of the list. (It's O(1).)
func (v vList) length() int {
if v.base == nil {
return 0
}
return len(v.base.ele)*2 - v.offset - 1
}
 
// A handy method: satisfy stringer interface for easy output.
func (v vList) String() string {
if v.base == nil {
return "[]"
}
r := fmt.Sprintf("[%v", v.base.ele[v.offset])
for sg, sl := v.base, v.base.ele[v.offset+1:]; ; {
for _, e := range sl {
r = fmt.Sprintf("%s %v", r, e)
}
sg = sg.next
if sg == nil {
break
}
sl = sg.ele
}
return r + "]"
}
 
// One more method for demonstration purposes
func (v vList) printStructure() {
fmt.Println("offset:", v.offset)
for sg := v.base; sg != nil; sg = sg.next {
fmt.Printf("  %q\n", sg.ele) // %q illustrates the string type
}
fmt.Println()
}
 
// demonstration program using the WP example data
func main() {
var v vList
fmt.Println("zero value for type. empty vList:", v)
v.printStructure()
 
for a := '6'; a >= '1'; a-- {
v = v.cons(vEle(a))
}
fmt.Println("demonstrate cons. 6 elements added:", v)
v.printStructure()
 
v = v.cdr()
fmt.Println("demonstrate cdr. 1 element removed:", v)
v.printStructure()
 
fmt.Println("demonstrate length. length =", v.length())
fmt.Println()
 
fmt.Println("demonstrate element access. v[3] =", v.index(3))
fmt.Println()
 
v = v.cdr().cdr()
fmt.Println("show cdr releasing segment. 2 elements removed:", v)
v.printStructure()
}
Output:
zero value for type.  empty vList: []
offset: 0

demonstrate cons. 6 elements added: [1 2 3 4 5 6]
offset: 1
  ["" "1" "2" "3"]
  ["4" "5"]
  ["6"]

demonstrate cdr. 1 element removed: [2 3 4 5 6]
offset: 2
  ["" "1" "2" "3"]
  ["4" "5"]
  ["6"]

demonstrate length. length = 5

demonstrate element access. v[3] = 5

show cdr releasing segment. 2 elements removed: [4 5 6]
offset: 0
  ["4" "5"]
  ["6"]

Kotlin[edit]

Translation of: Go
// version 1.1.3
 
class VList<T : Any?> {
 
private class VSeg {
var next: VSeg? = null
lateinit var ele: Array<Any?>
}
 
private var base: VSeg? = null
private var offset = 0
 
/* locate kth element */
operator fun get(k: Int): T {
var i = k
if (i >= 0) {
i += offset
var sg = base
while (sg != null) {
@Suppress("UNCHECKED_CAST")
if (i < sg.ele.size) return sg.ele[i] as T
i -= sg.ele.size
sg = sg.next
}
}
throw IllegalArgumentException("Index out of range")
}
 
/* add an element to the front of VList */
fun cons(a: T): VList<T> {
if (this.base == null) {
val v = VList<T>()
val s = VSeg()
s.ele = arrayOf<Any?>(a)
v.base = s
return v
}
if (this.offset == 0) {
val l2 = this.base!!.ele.size * 2
val ele = arrayOfNulls<Any>(l2)
ele[l2 - 1] = a
val v = VList<T>()
val s = VSeg()
s.next = this.base
s.ele = ele
v.base = s
v.offset = l2 - 1
return v
}
this.offset--
this.base!!.ele[this.offset] = a
return this
}
 
/* obtain a new VList beginning at the second element of an old VList */
fun cdr(): VList<T> {
if (base == null) throw RuntimeException("cdr invoked on empty VList")
offset++
if (offset < base!!.ele.size) return this
val v = VList<T>()
v.base = this.base!!.next
return v
}
 
/* compute the size of the VList */
val size: Int
get() {
if (base == null) return 0
return base!!.ele.size * 2 - offset - 1
}
 
override fun toString(): String {
if (base == null) return "[]"
var r = "[${base!!.ele[offset]}"
var sg = base
var sl = base!!.ele.sliceArray(offset + 1..base!!.ele.lastIndex)
while (true) {
for (e in sl) r += " $e"
sg = sg!!.next
if (sg == null) break
sl = sg.ele
}
return r + "]"
}
 
fun printStructure() {
println("Offset: $offset")
var sg = base
while (sg != null) {
println(sg.ele.contentToString())
sg = sg.next
}
println()
}
}
 
fun main(args: Array<String>) {
var v = VList<Int>()
println("Before adding any elements, empty VList: $v")
v.printStructure()
 
for (a in 6 downTo 1) v = v.cons(a)
println("Demonstrating cons method, 6 elements added: $v")
v.printStructure()
 
v = v.cdr()
println("Demonstrating cdr method, 1 element removed: $v")
v.printStructure()
 
println("Demonstrating size property, size = ${v.size}\n")
println("Demonstrating element access, v[3] = ${v[3]}\n")
 
v = v.cdr().cdr()
println("Demonstrating cdr method again, 2 more elements removed: $v")
v.printStructure()
}
Output:
Before adding any elements, empty VList: []
Offset: 0

Demonstrating cons method, 6 elements added: [1 2 3 4 5 6]
Offset: 1
[null, 1, 2, 3]
[4, 5]
[6]

Demonstrating cdr method, 1 element removed: [2 3 4 5 6]
Offset: 2
[null, 1, 2, 3]
[4, 5]
[6]

Demonstrating size property, size = 5

Demonstrating element access, v[3] = 5

Demonstrating cdr method again, 2 more elements removed: [4 5 6]
Offset: 0
[4, 5]
[6]

ooRexx[edit]

The ooRexx queue class is a vlist implementation. Here are some examples of usage:

 
-- show how to use the queue class
q = .queue~of(1, 2, 3, 4)
 
-- show indexed access to item
say q[4]
 
-- update an item
q[2] = "Fred"
 
-- show update and that other indexes are unchanged
say q[2] q[4]
 
-- push an item on the front and show the change in positions
q~push("Mike")
say q[1] q[2] q[4]
 
-- pop an item and show the change again
q~pull
say q[1] q[2] q[4]
 
 
Output:
4
Fred 4
Mike 1 3
1 Fred 4

Racket[edit]

See https://github.com/takikawa/tr-pfds/blob/master/pfds/vlist.rkt for an implementation of VLists.

REXX[edit]

This classic REXX version uses (mostly) the same "input" and operations as the ooRexx version, except that the (stack) queue isn't changed or used.

 ╔════════════════════════════════════════════════════════════════════╗
 ║                                                                    ║
 ║             ┌────────────┬───────────────────────────┐             ║
 ║             │  call  q   │                           │  (no args)  ║
 ║             └────────────┴───────────────────────────┘             ║
 ║ returns the number of items in the VList.                          ║
 ║                                                                    ║
 ║             ┌────────────┬───────────────────────────┐             ║
 ║             │  call  q   │  0,  a b c d  ∙∙∙         │             ║
 ║             └────────────┴───────────────────────────┘             ║
 ║ inserts the specified items(s) to the  front  of the VList.        ║
 ║                                                                    ║
 ║             ┌────────────┬───────────────────────────┐             ║
 ║             │  call  q   │  999999999,  a b c d ∙∙∙  │             ║
 ║             └────────────┴───────────────────────────┘             ║
 ║ appends the specified items(s) to the  end  of the VList.          ║
 ║                                                                    ║
 ║             ┌────────────┬───────────────────────────┐             ║
 ║             │  call  q   │  10,  a b c d  ∙∙∙        │             ║
 ║             └────────────┴───────────────────────────┘             ║
 ║ sets the tenth item to the items(s) specified.   If there're less  ║
 ║ than  10  items in the VList,  the specified item(s) are appended  ║
 ║ to the  end  of the VList.                                         ║
 ║                                                                    ║
 ║             ┌────────────┬───────────────────────────┐             ║
 ║             │  call  q   │  17                       │             ║
 ║             └────────────┴───────────────────────────┘             ║
 ║ returns the  seventeenth  item in the VList.                       ║
 ║                                                                    ║
 ║             ┌────────────┬───────────────────────────┐             ║
 ║             │  call  q   │  ,                        │  (a comma)  ║
 ║             └────────────┴───────────────────────────┘             ║
 ║ returns  all  the items in the VList.                              ║
 ║                                                                    ║
 ║             ┌────────────┬───────────────────────────┐             ║
 ║             │  call  q   │  -11                      │             ║
 ║             └────────────┴───────────────────────────┘             ║
 ║ deletes the  eleventh  item in the VList.                          ║
 ║                                                                    ║
 ║             ┌────────────┬───────────────────────────┐             ║
 ║             │  call  q   │  63.1,  a b c d  ∙∙∙      │             ║
 ║             └────────────┴───────────────────────────┘             ║
 ║ inserts the specified items after the  63rd  item.  If there's less║
 ║ then  63  items in the VList,  the specified items() are appended  ║
 ║ to the  end  of the VList.  Any non-zero decimal fraction may be   ║
 ║ used.       I.E.:     63.01     63.5     63.63     63.9            ║
 ╚════════════════════════════════════════════════════════════════════╝
/*REXX program demonstrates  VList  operations:   add,  update,  delete, insert,  show. */
/*could use instead: q = 1 2 3 4 */
call q 0, 1 2 3 4 /*populate the list with values 1 ── ►4*/
say q(4) /*show the indexed access to an item. */
 
call q 2, 'Fred' /*update (or add) the second item. */
say q(2) q(4) /*show second and fourth items in list.*/
/*zeroth item is inserted in the front.*/
call q 0, 'Mike' /*insert item in front of the list. */
say q(1) q(2) q(4) /*show first, second, and fourth items.*/
/*any negative number is deleted. */
call q -1 /*delete the first item in the list. */
say q(1) q(2) q(4) /*show the 1st, 2nd, and 4th items.*/
/*Fractional number inserts an item. */
call q 3.5, '3½' /*insert the item after the third item.*/
say q , /*show all the VList items. */
/*Put on a dog and pony show. */
say 'number of items in Vlist:' q() /*show and tell time for the Vlist. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
q: parse arg n 1 na 1 ni,!; w=words(q); $= /*obtain arguments; # items.*/
if symbol('Q')=='LIT' then q= /*var Q may not be defined. */
if arg()==0 then return words(q) /*return the VList item count*/
if arg(1, 'O') then return q /*return the whole shebang. */
if arg()==1 & n>0 then return word(q,n) /*1 positive arg? Return it.*/
if n==0 then do; q=! q; return q; end /*insert in front of the list*/
if n> w then do; q=q !; return q; end /*add it to end. " " " */
na=abs(n) /*we might need use of ABS. */
if \datatype(ni, 'W') & ni>0 then ni=trunc(na) /*Is this an insert>? TRUNC.*/
else ni=0 /*... No? Then a plain Jane.*/
do j=1 for w /* [↓] rebuild the Vlist. */
if j==na then do; if na==n then $=$ !; end /*replace the item in list. */
else $=$ word(q, j) /*an easy-peasy (re-)build. */
if j==ni then $=$ ! /*handle the "insert". */
end /*j*/
q=space($); return q /*elide superfluous blanks. */
output   when using the default input:
4
Fred 4
Mike 1 3
1 Fred 4
1 Fred 3 3½ 4
number of items in Vlist: 5

Scala[edit]

Library: 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.

A quote of Martin Odersky, his co-worker Phil Bagwell† invented the VList.

object VList extends App {
 
val emptyVlist1 = Vector.empty[Int]
val emptyVlist2 = Vector[Int]()
val emptyVlist3 = Vector()
 
val addedVlist1 = Vector(1, 2) :+ 6 :+ 10 :+ 12 :+ 42
 
assert((addedVlist1, addedVlist1.head) == (Vector(1, 2, 6, 10, 12, 42), 1), "Header or VList not OK")
 
val addedVlist2 = addedVlist1.head +: addedVlist1.tail.drop(1)
assert((addedVlist2, addedVlist2.head) == (Vector(1, 6, 10, 12, 42), 1), "First CDR not deleted.")
 
assert(addedVlist1.size == 6)
 
assert(addedVlist1(3) == 10, "Wrong element accesed.")
println("Successfully completed without errors.")
}