[zerofan]

I've written this several times in several ways using C++ (and I'll probably write it at least once more to make it better). In an early version I used an integer level as you came to, but it made the compiler very unhappy as it recursively tried to expand nested types at compile time (it couldn't figure out the recursive types would terminate in practice). Max template recursion of 256 if I remember correctly, even though you'd never instantiate past 45 or so on any machine in the world.

In a later version, I implemented the specializations as inheritance on the abstract FingerTree base class (verbose, but it works), and I added Leafs and Nodes. Leafs are FingerTrees that hold your data, and Nodes are FingerTrees that point to other FingerTree instance. This dodges the recursive types problem. I don't know much Haskell, but I think it would be the C++ equivalent of:

    data FingerTree a = EmptyLeaf
                    | SingleLeaf a
                    | DoubleLeaf a a
                    | TripleLeaf a a a
                    | EmptyNode
                    | SingleNode (FingerTree a)
                    | DoulbeNode (FingerTree a) (FingerTree a)
                    | TripleNode (FingerTree a) (FingerTree a) (FingerTree a)
                    | FingerSpine (FingerTree a) (FingerTree a) (FingerTree a)

Virtual methods on each specialization took the place of pattern matching. Not super elegant.