On Wednesday, May 23, 2012 20:51:31 Roman D. Boiko wrote: > On Wednesday, 23 May 2012 at 18:39:02 UTC, Stewart Gordon wrote: > > On 23/05/2012 16:05, Roman D. Boiko wrote: > > <snip> > > > >> I need some immutable collections for my D Compiler Tools > >> project, namely linked list, > >> red-black tree, and possibly some others. > > > > <snip> > > > > What's the point of an immutable red-black tree? > > > > The whole point of a red-black tree is to facilitate fast > > dynamic addition, removal and lookup of elements. > > > > 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. > > > > Stewart. > > Immutable collections in most cases have the same performance > characteristics as mutable ones. Space consumption may be higher, > but not necessarily. > > Instead of mutating a collection, a new one is returned each time > you add or remove an element. It shares most nodes with a > previous one.
In my personal experience, that's not true at all. I've seen _huge_ performance problems in Haskell when using a map. There may be cases where an immutable container may not pose large performance problems, but I would be _very_ wary of using immutable containers, and _very_ careful with them when I did. - Jonathan M Davis