YARD-README.md

Immutable Ruby

Efficient, immutable, and thread-safe collection classes for Ruby.

The immutable-ruby gem provides 6 Persistent Data Structures: {Immutable::Hash Hash}, {Immutable::Vector Vector}, {Immutable::Set Set}, {Immutable::SortedSet SortedSet}, {Immutable::List List}, and {Immutable::Deque Deque} (which works as an immutable queue or stack).

Whenever you modify an Immutable collection, the original is preserved and a modified copy is returned. This makes them inherently thread-safe and shareable. At the same time, they remain CPU and memory-efficient by sharing between copies. (However, you can still mutate objects stored in these collections. We don't recommend that you do this, unless you are sure you know what you are doing.)

Immutable collections are almost always closed under a given operation. That is, whereas Ruby's collection methods always return arrays, Immutable collections will return an instance of the same class wherever possible.

Where possible, Immutable collections offer an interface compatible with Ruby's built-in Hash, Array, Set, and Enumerable, to ease code migration. Also, Immutable methods accept regular Ruby collections as arguments, so code which uses Immutable can easily interoperate with your other Ruby code.

And lastly, Immutable lists are lazy, making it possible to (among other things) process "infinitely large" lists.

Using

To make the collection classes available in your code:

require "immutable"

Or if you prefer to only pull in certain collection types:

require "immutable/hash"
require "immutable/vector"
require "immutable/set"
require "immutable/sorted_set"
require "immutable/list"
require "immutable/deque"

Hash ({Immutable::Hash API Documentation})

Constructing an Immutable::Hash is almost as simple as a regular one:

person = Immutable::Hash[name: "Simon", gender: :male]
# => Immutable::Hash[:name => "Simon", :gender => :male]

Accessing the contents will be familiar to you:

person[:name]                       # => "Simon"
person.get(:gender)                 # => :male

Updating the contents is a little different than you are used to:

friend = person.put(:name, "James") # => Immutable::Hash[:name => "James", :gender => :male]
person                              # => Immutable::Hash[:name => "Simon", :gender => :male]
friend[:name]                       # => "James"
person[:name]                       # => "Simon"

As you can see, updating the hash returned a copy, leaving the original intact. Similarly, deleting a key returns yet another copy:

male = person.delete(:name)         # => Immutable::Hash[:gender => :male]
person                              # => Immutable::Hash[:name => "Simon", :gender => :male]
male.key?(:name)                    # => false
person.key?(:name)                  # => true

Since it is immutable, Immutable::Hash doesn't provide an assignment (Hash#[]=) method. However, Hash#put can accept a block which transforms the value associated with a given key:

counters = Immutable::Hash[evens: 0, odds: 0]
counters.put(:odds) { |n| n + 1 }   # => Immutable::Hash[:odds => 1, :evens => 0]

Or more succinctly:

counters.put(:odds, &:next)         # => {:odds => 1, :evens => 0}

This is just the beginning; see the {Immutable::Hash API documentation} for details on all Hash methods.

Vector ({Immutable::Vector API Documentation})

A Vector is an integer-indexed collection much like an immutable Array. Examples:

vector = Immutable::Vector[1, 2, 3, 4] # => Immutable::Vector[1, 2, 3, 4]
vector[0]                              # => 1
vector[-1]                             # => 4
vector.set(1, :a)                      # => Immutable::Vector[1, :a, 3, 4]
vector.add(:b)                         # => Immutable::Vector[1, 2, 3, 4, :b]
vector.insert(2, :a, :b)               # => Immutable::Vector[1, 2, :a, :b, 3, 4]
vector.delete_at(0)                    # => Immutable::Vector[2, 3, 4]

Other Array-like methods like #select, #map, #shuffle, #uniq, #reverse, #rotate, #flatten, #sort, #sort_by, #take, #drop, #take_while, #drop_while, #fill, #product, and #transpose are also supported. See the {Immutable::Vector API documentation} for details on all Vector methods.

Set ({Immutable::Set API Documentation})

A Set is an unordered collection of values with no duplicates. It is much like the Ruby standard library's Set, but immutable. Examples:

set = Immutable::Set[:red, :blue, :yellow] # => Immutable::Set[:red, :blue, :yellow]
set.include? :red                          # => true
set.add :green                             # => Immutable::Set[:red, :blue, :yellow, :green]
set.delete :blue                           # => Immutable::Set[:red, :yellow]
set.superset? Immutable::Set[:red, :blue]  # => true
set.union([:red, :blue, :pink])            # => Immutable::Set[:red, :blue, :yellow, :pink]
set.intersection([:red, :blue, :pink])     # => Immutable::Set[:red, :blue]

Like most immutable methods, the set-theoretic methods #union, #intersection, #difference, and #exclusion (aliased as #|, #&, #-, and #^) all work with regular Ruby collections, or indeed any Enumerable object. So just like all the other immutable collections, Immutable::Set can easily be used in combination with "ordinary" Ruby code.

See the {Immutable::Set API documentation} for details on all Set methods.

SortedSet ({Immutable::SortedSet API Documentation})

A SortedSet is like a Set, but ordered. You can do everything with it that you can do with a Set. Additionally, you can get the #first and #last item, or retrieve an item using an integral index:

set = Immutable::SortedSet['toast', 'jam', 'bacon'] # => Immutable::SortedSet["bacon", "jam", "toast"]
set.first                                           # => "bacon"
set.last                                            # => "toast"
set[1]                                              # => "jam"

You can also specify the sort order using a block:

Immutable::SortedSet.new(['toast', 'jam', 'bacon']) { |a,b| b <=> a }
Immutable::SortedSet.new(['toast', 'jam', 'bacon']) { |str| str.chars.last }

See the {Immutable::SortedSet API documentation} for details on all SortedSet methods.

List ({Immutable::List API Documentation})

Immutable::Lists have a head (the value at the front of the list), and a tail (a list of the remaining items):

list = Immutable::List[1, 2, 3]
list.head                    # => 1
list.tail                    # => Immutable::List[2, 3]

Add to a list with {Immutable::List#add}:

original = Immutable::List[1, 2, 3]
copy = original.add(0)      # => Immutable::List[0, 1, 2, 3]

Notice how modifying a list actually returns a new list.

Laziness

Immutable::List is lazy where possible. It tries to defer processing items until absolutely necessary. For example, the following code will only call Prime.prime? as many times as necessary to generate the first 3 prime numbers between 10,000 and 1,000,000:

require 'prime'

Immutable.interval(10_000, 1_000_000).select do |number|
  Prime.prime?(number)
end.take(3)
  # => 0.0009s

Compare that to the conventional equivalent which needs to calculate all possible values in the range before taking the first three:

(10000..1000000).select do |number|
  Prime.prime?(number)
end.take(3)
  # => 10s

Construction

Besides Immutable::List[] there are other ways to construct lists:

• {Immutable.interval Immutable.interval(from, to)} creates a lazy list equivalent to a list containing all the values between from and to without actually creating a list that big.

• {Immutable.stream Immutable.stream { ... }} allows you to creates infinite lists. Each time a new value is required, the supplied block is called. To generate a list of integers you could do:

  count = 0
  Immutable.stream { count += 1 }

• {Immutable.repeat Immutable.repeat(x)} creates an infinite list with x as the value for every element.

• {Immutable.replicate Immutable.replicate(n, x)} creates a list of size n with x as the value for every element.

• {Immutable.iterate Immutable.iterate(x) { |x| ... }} creates an infinite list where the first item is calculated by applying the block on the initial argument, the second item by applying the function on the previous result and so on. For example, a simpler way to generate a list of integers would be:

  Immutable.iterate(1) { |i| i + 1 }

  or even more succinctly:

  Immutable.iterate(1, &:next)

• {Immutable::List.empty} returns an empty list, which you can build up using repeated calls to {Immutable::List#add #add} or other List methods.

Core Extensions

{Enumerable#to_list} will convert any existing Enumerable to a list, so you can slowly transition from built-in collection classes to immutable.

{IO#to_list} enables lazy processing of huge files. For example, imagine the following code to process a 100MB file:

require 'immutable/core_ext'

File.open("my_100_mb_file.txt") do |file|
  lines = []
  file.each_line do |line|
    break if lines.size == 10
    lines << line.chomp.downcase.reverse
  end
end

Compare to the following more functional version:

File.open("my_100_mb_file.txt") do |file|
  file.map(&:chomp).map(&:downcase).map(&:reverse).take(10)
end

Unfortunately, though the second example reads nicely it takes many seconds to run (compared with milliseconds for the first) even though we're only interested in the first ten lines. Using #to_list we can get the running time back comparable to the imperative version.

File.open("my_100_mb_file.txt") do |file|
  file.to_list.map(&:chomp).map(&:downcase).map(&:reverse).take(10)
end

This is possible because IO#to_list creates a lazy list whereby each line is only ever read and processed as needed, in effect converting it to the first example.

See the {Immutable::List API documentation} for details on all List methods.

Deque ({Immutable::Deque API Documentation})

A Deque (or "double-ended queue") is an ordered collection, which allows you to push and pop items from both front and back. This makes it perfect as an immutable stack or queue. Examples:

deque = Immutable::Deque[1, 2, 3] # => Immutable::Deque[1, 2, 3]
deque.first                       # 1
deque.last                        # 3
deque.pop                         # => Immutable::Deque[1, 2]
deque.push(:a)                    # => Immutable::Deque[1, 2, 3, :a]
deque.shift                       # => Immutable::Deque[2, 3]
deque.unshift(:a)                 # => Immutable::Deque[:a, 1, 2, 3]

Of course, you can do the same thing with a Vector, but a Deque is more efficient. See the {Immutable::Deque API documentation} for details on all Deque methods.

Other Reading

• The structure which is used for Immutable::Hash and Immutable::Set: Hash Array Mapped Tries
• An interesting perspective on why immutability itself is inherently a good thing: Matthias Felleisen's Function Objects presentation.
• The immutable-ruby {file:FAQ.md FAQ}
• {file:CONDUCT.md Contributor's Code of Conduct}
• {file:LICENSE License}