Mastering data structures in Ruby — Persistent lists

Ale Miralles
Dec 11, 2018 · 8 min read
> list = (1)
> list.insert(2)
> list.print
(1, 2)
> list1 = List.new(1)
> list2 = List.insert(list1, 2)
> list1.print
(1)
> list2.print
(1, 2)

Persistent list interface

The interface of this data structure is strongly shaped after the interface of the singly linked list that we built in the first post of this series, but there is a significant difference though, on persistent lists, all methods are class methods. We cannot make calls directly on this data structure; since instances are immutable, all interactions happen thru class methods.

Methods

Implementation details

For the internal storage, we are going to use a modified version of the singly linked list from the first post of this series. We can not use the original version as is because we need read-only nodes to store values and a method that allows us to reuse nodes from a given position to the tail of the list.

Empty

This method creates an empty list. Its complexity is O(1).

def self.empty
list = LinkedList.new
list.freeze
end

Insert

This method inserts a new item into a read-only copy of the specified list and returns that copy.

def self.insert list, data
ret = self.copy list
ret.insert data
ret.freeze
end

Update

Updates an item into a read-only copy of the specified list and returns that copy.

  • Update the value on a new version of the target node.
  • Reuse elements from the node that’s next to the target node until we get to the end of the list.
def self.update list, node, data
ret = LinkedList.new
reuse = false
found = false
list.each do |nd|
unless found
found = (nd.data == node.data)
if found
ret.insert(data)
reuse = true
next
end
end
unless reuse
ret.insert(data)
else
# Reuse nodes from target to tail.
ret.reuse_from_node(nd)
break
end
end
ret.freeze
end

Remove

This method removes an item from a read-only copy of the specified list and returns that copy.

def self.remove list, node
ret = LinkedList.new
reuse = false
found = false
list.each do |nd|
unless found
found = (nd.data == node.data)
if found
reuse = true
next # skip the target node.
end
end
unless reuse
ret.insert(nd.data)
else
# Reuse nodes from target to tail.
ret.reuse_from_node(nd)
break
end
end
ret.freeze
end

Cat

This method creates a read-only list that contains a copy of all nodes from LHS (left-hand side) and RHS (right-hand side).

def self.cat lhs, rhs
ret = self.copy lhs
ret.cat rhs
ret.freeze
end

Len

This method returns the length of the given list.

def self.len list
list&.length || 0
end

Find First

This method finds the first occurrence of the given predicate applied to the specified list.

def self.find_first list, &predicate
return nil unless list
return list.find_first &predicate
end

Each

This method walks the specified list yielding one element at a time to the given block.

def self.each list, &block
return nil unless list
list.each &block
end

Print

This method prints the contents of the specified list. The complexity of this method is O(n).

def self.print list
unless list
print "empty"
else
list.print
end
end

Copy

This method is not part of the public API, but I decided to include it as part of the analysis of this interface because it is the only method that can mutate lists. What this method does is copy elements from the source list into a new list and return that list.

private
def self.copy src
dst = LinkedList.new
src.each { |node| dst.insert node.data }
dst
end

When to use persistent data structures

I like to think of persistence as a nice side effect of not being able to afford updates in place. So any use-case that meets that constraint would be a nice fit for this kind of data structures.

Data Structures From Scratch — Ruby Edition.

amiralles

Concise programming articles for those who code

Ale Miralles

Written by

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors.

amiralles

amiralles

Concise programming articles for those who code