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, leafs 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 and change a value defined by its index (in range 0..n-1).