I was about to cite Okasaki, but I found a detailed answer over there: http://stackoverflow.com/a/1990580 http://stackoverflow.com/a/1990580 > Note also that

I was about to cite Okasaki, but I found a detailed answer over there: http://stackoverflow.com/a/1990580 http://stackoverflow.com/a/1990580 > Note also that all of this discusses only asymptotic running times. Many techniques for implementing purely functional data structures give you a certain amount of constant factor slowdown, due to extra bookkeeping necessary for them to work, and implementation details of the language in question. The benefits of purely functional data structures may outweigh these constant factor slowdowns, so you will generally need to make trade-offs based on the problem in question.