Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Functional Vectors
Scheme
Branch: master

Fetching latest commit…

Cannot retrieve the latest commit at this time

Failed to load latest commit information.
examples
LICENSE
README.org
fectors.sls
pkg-list.scm
test-vicare.sps
tests.scm

README.org

Functional Vectors for Scheme

Functional programming needs functional data structures. This is an implementation of “vectors” (also called arrays), a finite map keyed by consecutive integers between 0 and n - 1, n being the length of the vector. Being functional, the structure is not observably mutatable, and so access to any version will always give the correct answer.

There are many possible implementations of the vector interface with different efficiency characteristics, the one contained prioritises “single threaded” use of vectors, that is, one in which access is most frequently to the last created version of the vector. Access to previously stored versions works correctly, though it will not be quite as efficient.

If your use case is not single threaded, I recommend using a tree based implementation, which has adequate characteristics for all versions of the vector. One such implementation is based on fingertrees and is provided as part of my pdfs package[1]

I’d like to thank David Van Horn, whose racket library brought this to my attention[2], and from whom I shamelessly stole the name, and transitively, Sylvain Conchon and Jean-Christophe Filliâtre for bringing it to his[3], and Henry Baker for coming up with the idea in the first place[4]. Also, Marco Maggi[5] who has graciously provided a test suite for Vicare Scheme.

Footnotes

[1] Purely Functional Data Structures for Scheme

[2] Fector: Persistent Functional Vectors for Racket

[3] A Persistent Union-Find Data Structure

[4] Shallow Binding in Lisp 1.5

[5] http://marcomaggi.github.com/

Something went wrong with that request. Please try again.