"I worked up a full implementation as well but I decided that it was too complicated to post in the blog. What I was really trying to get across was that immutable data structures were possible and not that hard; a full-on finger tree implementation was a bit too much for that purpose."

I am happy to correct my post and acknowledge that a previous C# implementation did exist. Hopefully, Eric will publish his implementation.

So, the work discussed here is most probably the first published Finger Tree  implementation in C#.

Background:
Created by Ralf Hinze and Ross Paterson in 2004, and based to a large extent on the work of Chris Okasaki on Implicit Recursive Slowdown and Catenable Double-Ended Queus, this data structure, to quote the abstract of the paper introducing Finger Trees, is:

"a functional representation of persistent sequences supporting access to the ends in amortized constant time, and concatenation and splitting in time logarithmic in the size of the smaller piece. Representations achieving these bounds have appeared previously, but 2-3 finger trees are much simpler, as are the operations on them. Further, by defining the split operation in a general form, we obtain a general purpose data structure that can serve as a sequence, priority queue, search tree, priority search queue and more."

Why the finger tree deserves to be called the Swiss knife of data structures can best be explained by again quoting the introduction of the paper:

"The operations one might expect from a sequence abstraction include adding and removing elements at both ends (the deque operations), concatenation, insertion and deletion at arbitrary points, finding an element satisfying some criterion, and splitting the sequence into subsequences based on some property. Many efficient functional implementations of subsets of these operations are known, but supporting more operations efficiently is difficult. The best known general implementations are very complex, and little used.
This paper introduces functional 2-3 finger trees, a general implementation that performs well, but is much simpler than previous implementations with similar bounds. The data structure and its many variations are simple enough that we are able to give a concise yet complete executable description using the functional programming language Haskell (Peyton Jones, 2003). The paper should be accessible to anyone with a basic knowledge of Haskell and its widely used extension to multiple-parameter type classes (Peyton Jones et al., 1997). Although the structure makes essential use of laziness, it is also suitable for strict languages that provide a lazy evaluation primitive."

Efficiency and universality are the two most attractive features of finger trees. Not less important is simplicity, as it allows easy understanding, straightforward implementation and uneventful maintenance.

Stacks support efficient access to the first item of a sequence only, queues and deques support efficient access to both ends, but not to an randomly-accessed item. Arrays allow extremely efficient O(1) access to any of their items, but are poor at inserting, removal, splitting and concatenation. Lists are poor (O(N)) at locating a randomly indexed item.

Remarkably, the finger tree is efficient with all these operations. One can use this single data structure for all these types of operations as opposed to having to use several types of data structures, each most efficient with only some operations.

Note also the words functional and persistent, which mean that the finger tree is an immutable data structure.

In .NET the IList<T> interface specifies a number of void methods, which change the list in-place (so the instance object is mutable). To implement an immutable operation one needs first to make a copy of the original structure (List<T>, LinkedList<T>, …, etc). An achievement of .NET 3.5 and LINQ is that the set of new extension methods (of theEnumerable class) implement immutable operations.

In the year 2008, Finger Tree implementations have been known only in a few programming languages: in Haskell, in , and in Scala. At least this is what the popular search engines say.

What about a C# implementation? In February Eric Lippert had a post in his blogabout finger trees. The C# code he provided does not implement all operations of a Finger Tree and probably this is the reason why this post is referred to by the Wikipedia only as "Example of 2-3 trees in C#", but not as an implementation of the Finger Tree data structure. Actually, he did have a complete implementation at that time (see the Update at the start of this post), but desided not to publish it.