A Faster Immutable List Datatype

The goal of this project is to explore implementing a list-like datatype with enhanced performance. Immutable linked lists are a core datatype in functional programming languages, proving particularly useful in concurrent programs due to the immutability. The most common operations programmers use on an immutable list include random access, sequential accesses, appending, and copy/writes. Unfortunately, sequential access requires a pointer dereference for each node meaning O(n) time which can significantly impact performance. Iteration is necessary for the most popular functions including fold and map and because the datatype is immutable, many changes one may want to make to a list, excluding operations like prepending or removing an element from the head, require allocating a new list which takes O(n) time. This project will design and implement a new immutable linked list datatype with improved performance for the most common operations by leveraging memory/cache locality and mechanical sympathy to improve performance in concurrent programs within the Typelevel ecosystem. The new datatype implements a generalization of the traditional linked list, one where each node contains a constant number of elements rather than one. These nodes, which we call blocks, each contain an array and a pointer to the next block. Deliverables: -Outline direction and priorities for the new datatype based on existing alternatives and how to best integrate in to the greater Typelevel ecosystem (improve performance in concurrent programs by integrating it in to other datatypes ex. Typelevel fs2's Channel) -Research and design the new datatype -Implement the interface for the new datatype -Benchmark and compare theoretical asymptotic bounds against existing immutable linked list-like data structures -Proper documentation and tests