On Wednesday, 23 May 2012 at 18:39:02 UTC, Stewart Gordon wrote:
When the tree is immutable, only lookup speed is of any real relevance, so you might as well create a perfectly balanced binary tree. Or even better, an array.
An array does not facilitate sharing common subsets between containers, which is usually what you are aiming for when designing immutable containers – the idea is to get away with immutability performance-wise because you don't have to copy much on the common mutation operations.
David
