The biggest benefit of a purely functional data structure for performance is the same as functional programming in general - they capture the problem in a way t

The biggest benefit of a purely functional data structure for performance is the same as functional programming in general - they capture the problem in a way that is easier for a compiler to reason about and rewrite to hardware-optimized forms; a computation problem addressed in functional style is going to have fewer ordering dependencies, and (depending on the language) a potentially richer, more expressive type system enabling more aggressive optimizations. Functional code happens to be particularly amenable to parallel optimization, so it's one of the go-to examples of what can be done. In a practical benchmarking scenario like gcc vs. GHC on the benchmarks game[0], gcc is still going to win most of the time. This is mainly a reflection of where the bulk of effort in compiler technology has gone, though, not a definitive "a purely functional data structure is going to be slower" statement. You're leaning a lot more on your compiler when trying to make functional languages run fast, and the biggest benefits of compiler optimizers are going to appear in the overall performance of applications, not benchmarks of an individual data structure. That said, there are also plenty of examples where a mutable structure just wins and nothing with equivalent performance is likely to appear in the functional world anytime soon. If you want to get into the details of that you have to look at each category of data structure case-by-case. [0] http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?test=all&lang=gcc&lang2=ghc&data=u64q http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?t...