Slide #1.

Java Programming Persistent Data Types
More slides like this


Slide #2.

Persistent Data Structure • A persistent data structure is a data structure having an internal state that never changes. – No operation affects the public state of the data structure. – Any operation that would produce a state change in a non-persistent structure, will instead produce a new data structure that reflects the updated state. – In this discussion, the term ‘persistent’ does not mean ‘saved’ • We will describe a list as having two parts – first: the first element in the list – rest: a list of the remaining elements in the list
More slides like this


Slide #3.

Persistent List public interface PersistentList { // READ ONLY public boolean isEmpty(); public int size(); public E get(int index); public E first(); public boolean contains(Object obj); public boolean containsAll(PersistentList other); } // STATE CHANGING OPERATIONS public PersistentList rest(); public PersistentList append(PersistentList public PersistentList reverse(); public PersistentList add(E elem); public PersistentList addAll(PersistentList suffix); other);
More slides like this


Slide #4.

Persistent List public abstract class AbstractPersistentList implements PersistentList { @Override public PersistentList addAll(PersistentList other) { PersistentList result = this; while(!other.isEmpty()) { result.add(other.first()); other = other.rest(); } return result; } @Override public boolean containsAll(PersistentList other) { while(!other.isEmpty()) { if(!this.contains(other.first())) return false; } return true; } } // we can also do “add” but will write this method later
More slides like this


Slide #5.

EmptyPersistentList public class EmptyPersistentList extends AbstractPersistentList { public EmptyPersistentList() { } public boolean isEmpty() { return true; } public E first() { throw new EmptyListException(); } public PersistentList rest() { throw new EmptyListException(); } public E get(int index) { throw new IndexOutOfBoundsException(); } public int size() { return 0; } public boolean contains(Object obj) { return false; } public PersistentList append(PersistentList suffix) { return suffix; } public PersistentList reverse() { return this; } } public PersistentList add(E elem) { return new NonEmptyPersistentList(elem, this); }
More slides like this


Slide #6.

EmptyPersistentList public public class class NonEmptyPersistentList NonEmptyPersistentList extends extends AbstractPersistentList AbstractPersistentList { { private private final final E E first; first; private private final final PersistentList PersistentList rest; rest; public public NonEmptyPersistentList(E NonEmptyPersistentList(E first, first, PersistentList PersistentList rest) rest) { { this.first this.first = = first; first; this.rest this.rest = = rest; rest; } } public public E E get(int get(int index) index) { { if(index if(index == == 0) 0) { { return return first; first; } } else else { { return return rest.get(index-1); rest.get(index-1); } } } } public public int int size() size() { { return return 1 1 + + rest.size(); rest.size(); } } public public E E first() first() { { return return first; first; } } public public PersistentList PersistentList rest() rest() { { return return rest; rest; } } public public PersistentList PersistentList append(PersistentList append(PersistentList suffix) suffix) { { return new NonEmptyPersistentList(first, rest.append(suffix)); return new NonEmptyPersistentList(first, rest.append(suffix)); } } public public PersistentList PersistentList reverse() reverse() { { return return rest.reverse().append(new rest.reverse().append(new NonEmptyPersistentList(first, NonEmptyPersistentList(first, new new EmptyPersistentList())); EmptyPersistentList())); } } public public boolean boolean contains(Object contains(Object obj) obj) { { return return first.equals(obj) first.equals(obj) || || rest.contains(obj); rest.contains(obj); } } public public boolean boolean isEmpty() isEmpty() { { return return false; false; } } public public PersistentList PersistentList add(E add(E elem) elem) { { return return new new NonEmptyPersistentList(elem, NonEmptyPersistentList(elem, this); this); } } } }
More slides like this


Slide #7.

How to use a persistent list • Can we write a function to create a list of N random values in [0-1)? public static PersistentList getRandomList(int n) { PersistentList randoms = new EmptyPersistentList<>(); for(int i = 0; i < n; i++){ randoms = new NonEmptyPersistentList(Math.random(), randoms); } return randoms; } • Can we write a function to convert an array of elements into a persistent list? public static PersistentList toList(E[] data) { PersistentList result = new EmptyPersistentList<>(); for(int i=data.length-1; i>=0; i--) { result = new NonEmptyPersistentList<>(data[i], result); } return result; } • Can we write a function to modify the state of a PersistentList? public static void modifyState(PersistentList list) { /// what could I write to modify the state of list? }
More slides like this