[fusiongyro]

Haskell's Data.Sequence is based on finger trees. I'd be surprised if the Real World Haskell guys would recommend it so strongly if it performed "very"^N badly. They're well-known for being performance-obsessed.

"Both Haskell's built-in list type and the DList type that we defined above have poor performance characteristics under some circumstances. The Data.Sequence module defines a Seq container type that gives good performance for a wider variety of operations." -- http://book.realworldhaskell.org/read/data-structures.html#d...

[carterschonwald]

Indeed. As one of those performance obsessed haskellers, a golden rule is "choose your data structures based upon your work load". This means not just the time space complexity of the operations , but also whether you want persistence vs shared state. Etc etc. finger trees are nice for workloads that are heavy on adding / removing values on the ends, with some random access, sequential scans are ok too.

I may wind up using this or a similar data structure in a number of current commercial and open source projects