This is an F# immutable list data structure based on balanced trees.
This data structure can be used wherever the ImmutableList<T> from Microsoft's immutable collections can be used, but the interface of this library follows F# idioms more closely.
Since F# already offers immutable sets and maps, it might be easier to drop this into your project than to take a dependency on the immutable collections. (I really like using Microsoft's immutable collections in C#, actually...)
This implementation is based on 2-3 trees which are a precursor of red-black trees. I learned about 2-3 trees from a book by Robert Sedgewick, and I wrote prototypes of this code in Scheme and OCaml before porting it to F#.
Operations such as insertion, replacement, and deletion occur in logarithmic time.
Although the solution and project files were created with VS 2017, the F# code should probably run on implementations as old as VS 2010. This project compiles the code for .NET Standard 2.0.
A compiled version of this code is available on NuGet as Sunlighter.TreeListLib.