Implement a Persistent Immutable List in JavaScript

Persistent data structures are valuable for scenarios where you need to maintain historical versions of data without expensive copying. This challenge asks you to implement a persistent, immutable list data structure in JavaScript, allowing you to efficiently create new versions of the list upon modification.

Problem Description

Your task is to create a JavaScript class, PersistentList, that represents an immutable list. When you perform an operation that would typically modify a list (like adding or removing an element), instead of altering the original list, your implementation should return a new PersistentList instance representing the modified state. The original PersistentList instances must remain unchanged. This immutability and persistence are achieved by sharing common underlying data between different versions of the list.

Key Requirements:

• Immutability: All operations that conceptually modify the list must return a new PersistentList instance. The original instance must not be altered.
• Persistence: Different versions of the list should efficiently share their underlying data. This means that if you create a new version of a list, it should ideally reuse as much of the original list's structure as possible.
• Core List Operations: Implement the following methods:
  • add(element): Returns a new PersistentList with element appended to the end.
  • get(index): Returns the element at the specified index.
  • size(): Returns the number of elements in the list.
  • remove(index): Returns a new PersistentList with the element at index removed.
  • set(index, element): Returns a new PersistentList with the element at index replaced by element.
• Efficient Sharing: While not strictly enforced by tests in this challenge, the design should lend itself to efficient sharing of data (e.g., using a tree-like structure internally).

Expected Behavior:

• Creating a PersistentList with initial elements should be possible.
• Calling add, remove, or set on a PersistentList should yield a new PersistentList instance. The original list should be unchanged.
• Accessing elements via get should work correctly on all versions of the list.

Edge Cases:

• Empty list operations.
• Operations on indices out of bounds (e.g., get, remove, set with invalid indices). You should handle these gracefully (e.g., by throwing errors or returning specific values as appropriate for list behavior).

Examples

Example 1:

let list1 = new PersistentList([1, 2, 3]);
console.log(list1.size()); // Output: 3
console.log(list1.get(1)); // Output: 2

let list2 = list1.add(4);
console.log(list1.size()); // Output: 3 (original list unchanged)
console.log(list1.get(3)); // Output: undefined (original list does not have index 3)
console.log(list2.size()); // Output: 4
console.log(list2.get(3)); // Output: 4
console.log(list2.get(2)); // Output: 3 (shares data with list1)

Explanation: list1 is initialized. add(4) creates list2 with 4 appended. list1 remains unmodified. list2 correctly reflects the addition.

Example 2:

let listA = new PersistentList(['a', 'b']);
let listB = listA.set(0, 'x');
let listC = listB.remove(1);

console.log(listA.get(0)); // Output: 'a'
console.log(listA.size()); // Output: 2

console.log(listB.get(0)); // Output: 'x'
console.log(listB.get(1)); // Output: 'b'
console.log(listB.size()); // Output: 2

console.log(listC.get(0)); // Output: 'x'
console.log(listC.size()); // Output: 1

Explanation: listA is the original. listB is a new list with the first element changed. listC is a new list with the second element of listB removed. All original lists retain their state.

Example 3: (Edge Case: Empty List)

let emptyList = new PersistentList([]);
console.log(emptyList.size()); // Output: 0

let listAfterAdd = emptyList.add(10);
console.log(emptyList.size()); // Output: 0
console.log(listAfterAdd.size()); // Output: 1
console.log(listAfterAdd.get(0)); // Output: 10

try {
    emptyList.get(0);
} catch (e) {
    console.log("Caught expected error for get on empty list."); // Output: Caught expected error for get on empty list.
}

Explanation: Operations on an empty list should behave as expected, creating new lists with the added elements and throwing errors for invalid index access.

Constraints

• The PersistentList class should be implemented in JavaScript.
• The internal representation should aim for efficient sharing of data to avoid full deep copies on modification. Consider techniques like path copying or node sharing if you are familiar with them.
• The get operation should have a time complexity of O(log n) or O(1) in the average case, where n is the number of elements in the list.
• The add, remove, and set operations should have a time complexity of O(log n) or O(1) in the average case, where n is the number of elements in the list.
• The total memory usage should be proportional to the sum of the lengths of all created list versions, not the product.

Notes

This challenge focuses on the fundamental principles of persistent data structures. You might consider using an array-based internal representation that is cleverly structured to enable sharing. Think about how an update at a specific index can affect only a small portion of the underlying structure. For an advanced solution, research techniques like "finger trees" or "balanced trees" adapted for persistence. For a simpler yet still effective approach, consider a form of path copying within an array or tree-like structure. You don't need to implement a full-blown balanced tree if a simpler array-based approach can achieve the desired persistence properties, though a tree-based approach would typically offer better asymptotic performance for all operations.