This is a (currently WIP) repository of immutable, persistent data structures in Common Lisp. My dream is that someday it will rival Clojure's standard library collection types.
Modern CL code has access to :package-local-nicknames
in defpackage
and
uiop:define-package
. We can expect the main way of using IMMUTABLE to be by
local-nicknaming immutable/vec
to vec
, or immutable/map
to map
, and referring to
operators like vec:length
and vec:ref
. This means that operator names should be
concise, and need not include their type to disambiguate. IMMUTABLE's packages should
shadow CL symbols liberally to accomplish this.
-
vec
- bit-partitioned tries with tails- type definition -
vec
- indexing -
ref
- examine length -
length
-
emptyp
-
- rewrite various operators to not use generators where unnecessary
- internal iteration facility -
generate-vec
- convert from CL sequences -
from-list
andfrom-vector
- convert to CL sequences -
to-list
andto-vector
- constructor analogous to
list
andvector
-vec
- append one to end -
push-back
- pop one from end -
pop-back
- append multiple to end -
extend
-
extend-from-vector
-
extend-from-list
-
- concatenate vecs -
concatenate
- remove multiple from end -
retract
- replace element at given index -
replace-at
- update element at given index by function -
update-at
- convenient iteration constructs
-
map
- apply function to each element, collect result to newvec
-
for-each
- apply function to each element, discard result -
do
- macro analogous todolist
-
iterate
integration -FOR elt IN-VEC vec
- sequence keywords
-
start
-
end
-
from-end
-
-
- equality testing -
equal
- hashing?
- transients - see Jean Niklas L'orange's blog post
- representation for transient ids
- make
vec
transient -transient!
- make transient persistent -
persistent
- append one to end -
push-back!
- pop one from end
- append multiple to end -
extend!
- remove multiple from end
- trivial-extensible-sequences integration
- define
vec
as astandard-class
subclassingsequences:sequence
- use
standard-instance-access
when available to optimize slot access
- use
- method on
sequences:length
which callslength
- method on
sequences:elt
which callsref
- method on
make-simple-sequence-iterator
- method on
iterator-element
- method on
iterator-step
- method on
iterator-endp
- method on
iterator-element
- method on
iterator-index
- method on
iterator-copy
- method on
- method on
concatenate
when RESULT-PROTOTYPE and the first sequence arevec
s to share structure with the first sequence - no-op method on
copy-seq
- method on
emptyp
- method on
map
- define
- type definition -
-
hash
- generic hashing and equality for use bydict
- core FxHash algorithm
- hashing and equality for builtin types, and tests
-
fixnum
-
integer
-
float
-
single-float
-
double-float
- do implementations with
short-float
andlong-float
actually exist?
-
-
character
-
complex
-
ratio
-
vector
-
string
-
simple-base-string
-
base-string
-
simple-string
- generic
string
-
-
bit-vector
-
simple-bit-vector
- generic
bit-vector
-
-
simple-vector
- generic
vector
-
-
array
-
cons
-
symbol
- generic function for user-defined methods
- MOP-ey default method for
standard-object
andcondition
- MOP-ey default method for
-
-
==
wrapper -
hash
wrapper which returnsunsigned-fixnum
-
dict
- hash array mapped tries- type definition
- generic over hash and equality functions
- lookup
- generic over hash and equality functions
- tests
- optimize node definitions to store key/value pairs inline.
- convenient internal iterators over the children of a
hash-node
orconflict-node
?
- convenient internal iterators over the children of a
- internal iteration facility
- convert from CL collections
-
from-hash-table
- test behavior with
:convert-overwrite t
- test behavior with
:convert-overwrite nil
- test behavior with
-
from-alist
- test behavior with
:convert-overwrite t
- test behavior with
:convert-overwrite nil
- test behavior with
-
from-plist
- test basic behavior
- test behavior with
:convert-overwrite t
- test behavior with
:convert-overwrite nil
-
- convert to CL collections
-
to-hash-table
-
to-alist
-
to-plist
- test basic behavior
-
- convenient constructor -
dict
- insert one pair
- tests
- remove one pair
- tests
- user-friendly print-object
- print-object for transients?
- test that same hash and test functions imply same structure after various operations
- insertion in random order
- removal
- replacement
- insert multiple pairs -
insert-multiple
- tests
- remove multiple pairs -
remove-multiple
- tests
- combine two maps -
union
- check for compatible hash and equality functions
- solve equality testing on arbitrary closures /s
- fall back to
reduce
ofinsert
when the hash and equality functions are noteq
- structural merge when the hash and equality functions are
eq
- accept a
merge-entries
function of type(function (key value value) (values value &optional))
to avoid left- or right-bias
- check for compatible hash and equality functions
- convenient iteration constructs
-
map-values
- apply function to each value, leaving keys untouched, collect to newdict
-
for-each
- apply function to each pair, discard result -
do
- macro analogous todolist
-
iterate
integration?
-
- equality testing
-
rehash
- change hash and test function ofdict
- implementation
- tests
- hashing?
- transients
- representation for transient ids
- make dict transient -
transient!
- add one pair
- add multiple pairs?
- remove one pair
- remove multiple pairs?
- integration with trivial-extensible-sequences?
- type definition
-
rope
- ropes of characters as strings- type definition
- node for strings
- specialize on string subtypes?
- node for concatenation
- node for substring
- node for strings
- short node optimization to avoid unnecessary indirections
- experiment with different cutoffs to balance between cost of copying and cost of indirection
- lookup
- internal iteration facility
- convert from CL strings
- convert to CL strings
- convenient constructor?
- output to stream without converting to string
- type definition