On Wednesday, 23 May 2012 at 21:12:04 UTC, Jonathan M Davis wrote:
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
While I am an Haskell newbie, I think most of those problems are
related to how hard it is for many developers to learn how to
properly
optimize Haskell code.
The straightforward way to do some things is not the most
performant, and
some optimizations require fine tuning of strict/lazy semantics
on the
data structures manipulations.
--
Paulo
