FP Homework 3

Immutable data types

1 - Immutable Array

Study materials for immutable (persistent) arrays are at: https://en.wikipedia.org/wiki/Persistent_data_structure or https://en.wikipedia.org/wiki/Persistent_array

Let's have a class representing a triple or triplet, where the values can be set only once at the beginning, when we are creating an instance of this class.

An example can be following class implemented in C#:

abstract class Triple<A>
{
  private readonly A[] data = new A[3];
  public Triple(A left, A middle, A right)
  {
    data[0] = left;
    data[1] = middle;
    data[2] = right;
  }
  public A this[int index]
  {
    get => index switch
    {
      >= 0 and <= 2 => this.data[index],
      _ => throw new IndexOutOfRangeException($"Index {index} out of range for a triplet.")
    };
  }
}

Now, build an array composed from these triples. The individual triples will be used to store values and to store references. Internally, the array will be represented as a ternary tree composed from these triples. In this tree, leaves are values stored in these triples and branches are references stored in these triples.

For such immutable array create:

• Constructor - a way to define an array of given size n (an array to store n values).
• Enumerator - a way to go trough the array and get all values.
• Indexer - a way how to get a value defined by its index (in range 0..n-1).
• Set method - a way, ho to change a value in the array based on its index. While it is an immutable array, this method needs to return the new array that accommodated the change.