Efficient, thread-safe immutable data structures for Crystal.
Whenever an Immutable
data structure is "modified", the original remains
unchanged and a modified copy is returned. However, the copy is efficient due to
structural sharing. This makes Immutable
data structures inherently
thread-safe, garbage collector friendly and performant.
At the moment, Immutable
implements the following persistent data structures:
Immutable::Vector
: array-like ordered, integer-indexed collection
implementing efficient append, pop, update and lookup operationsImmutable::Map
: hash-like unordered key-value collection implementing
efficient lookup and update operationsAdd this to your application's shard.yml
:
dependencies:
immutable:
github: lucaong/immutable
For a list of all classes and methods refer to the API documentation
To use the immutable collections, require immutable
in your code:
require "immutable"
# Vector behaves mostly like an Array:
vector = Immutable::Vector[1, 2, 3, 4, 5] # => Vector [1, 2, 3, 4, 5]
vector[0] # => 1
vector[-1] # => 5
vector.size # => 5
vector.each { |elem| puts elem }
# Updating a Vector always returns a modified copy:
vector2 = vector.set(2, 0) # => Vector [1, 2, 0, 4, 5]
vector2 = vector2.push(42) # => Vector [1, 2, 0, 4, 5, 42]
# The original vector is unchanged:
vector # => Vector [1, 2, 3, 4, 5]
# Bulk updates can be made faster by using `transient`:
vector3 = vector.transient do |v|
1000.times { |i| v = v.push(i) }
end
# Map behaves mostly like a Hash:
map = Immutable::Map[{:a => 1, :b => 2 }] # => Map {:a => 1, :b => 2}
map[:a] # => 1
# Updating a Map always returns a modified copy:
map2 = map.set(:c, 3) # => Map {:a => 1, :b => 2, :c => 3}
map2 = map2.delete(:b) # => Map {:a => 1, :c => 3}
# The original map in unchanged:
map # => Map {:a => 1, :b => 2}
# Bulk updates can be made faster by using `transient`:
map3 = Immutable::Map(String, Int32)[]
map3 = map3.transient do |m|
1000.times { |i| m = m.set(i.to_s, i) }
end
# Nested arrays/hashes can be turned into immutable versions with the `.from`
# method:
nested = Immutable.from({:name => "Ada", :colors => [:blue, :green, :red] })
nested # => Map {:name => "Ada", :colors => Vector [:blue, :green, :red]}
Immutable::Vector
is implemented as a bit-partitioned vector trie with a block
size of 32 bits, that guarantees O(Log32) lookups and updates, which is
effectively constant time for practical purposes. Due to tail optimization,
appends and pop are O(1) 31 times out of 32, and O(Log32) 1/32 of the times.
Immutable::Map
uses a bit-partitioned hash trie with a block size of 32 bits,
that also guarantees O(Log32) lookups and updates.
Although not a port, this project takes inspiration from similar libraries and persistent data structure implementations like:
When researching on the topic of persistent data structure implementation, these blog posts have been of great help:
Big thanks to their authors for the great job explaining the internals of these data structures.