Crate im [−] [src]
Immutable Data Structures for Rust
This library implements several of the more commonly useful immutable data structures for Rust. They rely on structural sharing to keep most operations fast without needing to mutate the underlying data store, leading to more predictable code without necessarily sacrificing performance.
Because Rust is not a garbage collected language, and
immutable data structures generally rely on some sort of
garbage collection, values inside these data structures
are kept inside Arc
s. Methods will generally accept either
owned values or Arc
s and perform conversion as needed, but
you'll have to expect to receive Arc
s when iterating or
performing lookup operations. All caveats about using
reference counted values apply in general (eg. reference
counting is simplistic and doesn't detect loops).
A design goal of this library is to make using immutable
data structures as easy as it is in higher level
languages, but obviously there's only so much you can do.
Methods will generally attempt to coerce argument values
where they can: where an Arc
is called for, it will be
able to figure out how to convert whatever is provided
into an Arc
if it isn't already.
It's also been a design goal to provide as complete an
API as possible, which in a practical sense has meant
going over the equivalent implementations for Haskell to
ensure the API covers the same set of use cases. This
obviously doesn't include things like Foldable
and
Functor
which aren't yet expressible in Rust, but in
these cases we've tried to make sure Rust iterators are
able to perform the same tasks.
Care has been taken to use method names similar to those
in Rust over those used in the source material (largely
Haskell) where possible (eg. List::new()
rather than
List::empty()
, Map::get()
rather than Map::lookup()
).
Where Rust equivalents don't exist, terminology tends to
follow Haskell where the Haskell isn't too confusing,
or, when it is, we provide more readily understandable
aliases (because we wouldn't want to deprive the user
of their enjoyment of the word 'snoc
,'
even though it's reportedly not an obviously intuitive term).
Why Immutable Data Structures
Programming with immutable values, meaning that references to values can be relied on to always point to the same value, means that you can stop worrying about other parts of your code tampering with a value you're working on unexpectedly, or from unexpected parts of your code, making it a lot easier to keep track of what your code is actually doing.
Mutable values are, generally, a huge source of unexpected behaviour that a lot
of languages, like Haskell, Elm and Clojure, have been designed to avoid
altogether. Rust, being what it is, does a good job of discouraging this kind
of behaviour, and keeping it strictly controlled when it's necessary, but the
standard library doesn't provide collection data structures which are optimised
for immutable operations. This means, for instance, that if you want to add
an item to a Vec
without modifying it in place, you first need
to clone
the whole thing before making your change.
Data structures exist which are designed to be able to make these copies much
cheaper, usually by sharing structure between them, which, because this structure
is also immutable, is both cheap and safe. The most basic example of this kind
of data structure is the ConsList
, where, if you have a
list L and you want to push an item I to the front of it, you'll get back a new
list which literally contains the data 'item I followed by list L.' This operation
is extremely inexpensive, but of course this also means that certain other operations
which would be inexpensive for a Vec
are much more costly for a
ConsList
—index lookup is an example of this, where for a
Vec
it's just a matter of going to memory location
index times item size inside the Vec
's memory buffer, but for
a ConsList
you'd have to walk through the entire list from
the start, following references through to other list nodes, until you get to the
right item.
While all immutable data structures tend to be less efficient than their mutable
counterparts, when chosen carefully they can perform just as well for the operations
you need, and there are some, like List
and HashMap
,
which have performance characteristics good enough for most operations that you can
safely choose them without worrying too much about whether they're going to be the
right choice for any given use case. Better yet, some of them can even be safely
mutated in place when they aren't sharing any structure with other instances,
making them nearly as performant as their mutable counterparts.
Data Structures
We'll attempt to provide a comprehensive guide to the available data structures below.
Performance Notes
If you're not familiar with big O notation, here's a quick cheat sheet:
O(1) means an operation runs in constant time: it will take the same time to complete regardless of the size of the data structure.
O(n) means an operation runs in linear time: if you double the size of your data structure, the operation will take twice as long to complete; if you quadruple the size, it will take four times as long.
O(log n) means an operation runs in logarithmic time: if you double the size of your data structure, the operation will take roughly one step longer to complete; if you quadruple the size, it will need two steps more; and so on.
O(1)* means 'amortised O(1),' which means that an operation usually runs in constant time but will sometimes be more expensive, as much as O(n) for some data structures.
Lists
Lists are ordered sequences of single elements, usually with cheap push/pop operations, and index lookup tends to be O(n). Lists are for collections of items where you expect to iterate rather than lookup.
Type | Constraints | Order | Push Front | Pop Front | Push Back | Pop Back |
---|---|---|---|---|---|---|
List<A> |
insertion | O(1)* | O(1)* | O(1)* | O(1)* | |
ConsList<A> |
insertion | O(1) | O(1) | O(n) | O(n) |
Maps
Maps are mappings of keys to values, where the most common read operation is to find the value associated with a given key. Maps may or may not have a defined order. Any given key can only occur once inside a map, and setting a key to a different value will overwrite the previous value.
Type | Key Constraints | Order | Insert | Remove | Lookup |
---|---|---|---|---|---|
HashMap<K, V> |
Hash + Eq |
undefined | O(1)* | O(1)* | O(1)* |
OrdMap<K, V> |
Ord |
sorted | O(log n) | O(log n) | O(log n) |
Sets
Sets are collections of unique values, and may or may not have a defined order. Their crucial property is that any given value can only exist once in a given set.
Values in sets, in practice, behave exactly like keys in maps, and are therefore
normally implemented as maps from type A
to type ()
.
Type | Constraints | Order | Insert | Remove | Lookup |
---|---|---|---|---|---|
HashSet<A> |
Hash + Eq |
by hash | O(1)* | O(1)* | O(1)* |
OrdSet<A> |
Ord |
sorted | O(log n) | O(log n) | O(log n) |
Queues
Queues are specialised data structures where you can only append items to the end of the queue, and pop them off the front.
Strictly speaking, these queues are called FIFO queues ("first in, first out"), and there are other types of queue in which items go in and come out in different ways, but we currently only provide this one type.
Type | Constraints | Ordering | Push | Pop |
---|---|---|---|---|
Queue<A> |
FIFO | O(1)* | O(1)* |
In-place Mutation
Some data structures (currently only HashMap
), support
in-place copy-on-write mutation, which means that if you're the sole
user of a data structure, you can update it in place with a huge performance
benefit (about an order of magnitude faster than immutable operations, almost
as fast as std::collections
's mutable data structures).
Thanks to Arc
's reference counting, we are able to determine
whether a node in a data structure is being shared with other data structures,
or whether it's safe to mutate it in place. When it's shared, we'll automatically
make a copy of the node before modifying it, thus preserving the usual guarantees
you get from using an immutable data structure.
Reexports
pub use ordmap::OrdMap; |
pub use hashmap::HashMap; |
pub use ordset::OrdSet; |
pub use hashset::HashSet; |
pub use queue::Queue; |
pub use list::List; |
pub use conslist::ConsList; |
pub use iter::unfold; |
Modules
conslist |
A cons list. |
hash |
Tools for hashing. |
hashmap |
A hash map. |
hashset |
A hash set. |
iter |
Iterators over immutable data. |
lens |
A view into a data structure. |
list |
A catenable list. |
ordmap |
An ordered map. |
ordset |
An ordered set. |
queue |
A strict queue. |
shared |
Automatic |
Macros
conslist |
Construct a list from a sequence of elements. |
hashmap |
Construct a hash map from a sequence of key/value pairs. |
hashset |
Construct a set from a sequence of values. |
lens |
Construct a lens into a struct, or a series of structs. |
list |
Construct a list from a sequence of elements. |
ordmap |
Construct a map from a sequence of key/value pairs. |
ordset |
Construct a set from a sequence of values. |
Type Definitions
Map | |
Set |