Given the number of comments about the inefficiency of finger trees: yes they usually have a high constant factor (for their otherwise reasonable asymptotic com

Given the number of comments about the inefficiency of finger trees: yes they usually have a high constant factor (for their otherwise reasonable asymptotic complexity) due to cache misses. However, they are immutable and persistent, which means they have efficient sharing, which in turn makes them good candidates for * use in multiple threads at once * code that needs to be proven correct (I believe the Haskell Data.Sequence implementation is a translated from Coq)