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.

On Wednesday, 23 May 2012 at 18:51:32 UTC, Roman D. Boiko wrote:
> 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.

I've posted some links with information on this topic: http://d-coding.com/2012/05/21/functional-data-structures.html

It is also easy to find other sources on this topic for those who are interested.

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

On Wed, 23 May 2012 14:32:57 -0400, Roman D. Boiko <rb@d-coding.com> wrote:

> On Wednesday, 23 May 2012 at 18:24:28 UTC, simendsjo wrote:
>> On Wed, 23 May 2012 20:18:54 +0200, simendsjo <simendsjo@gmail.com> wrote:
>>
>>> On Wed, 23 May 2012 17:05:21 +0200, Roman D. Boiko <rb@d-coding.com> wrote:
>>>
>>>> I need some immutable collections for my D Compiler Tools project, namely linked list, red-black tree, and possibly some others.
>>>> So I'm going to create them for my use, and later generalize. I've created a project on GitHub, but didn't implement anything useful yet.
>>>
>>> http://dlang.org/phobos/std_container.html#SList
>>> http://dlang.org/phobos/std_container.html#RedBlackTree
>>
>> And http://dsource.org/projects/dcollections
>
> Those aren't immutable either :(

There is a very good reason however :)

I need tail-immutable and tail-const structs to be able to avoid "code pasting hell".

Until then, I feel very unmotivated to do anything regarding const and immutability.

FWIW, std.container.RedBlackTree is derived from dcollections.RBTree.

Regarding sharing structure, the class type would have to be specifically written to use this.  It's not just slapping on immutable tags.

For at least RBTree, and my implementation of Hash, this would not be feasible.

Certainly ArrayList, LinkedList, and probably Deque, they could share structure

If you need a sorted tree structure that supports sharing immutable state, you likely have to find a different algorithm than redblack, since adding nodes can modify the tree structure via rotates.

-Steve

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

On 5/23/12 1:53 PM, Roman D. Boiko wrote:
> On Wednesday, 23 May 2012 at 18:51:32 UTC, Roman D. Boiko wrote:
>> 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.
>
> I've posted some links with information on this topic:
> http://d-coding.com/2012/05/21/functional-data-structures.html
>
> It is also easy to find other sources on this topic for those who are
> interested.

Okasaki put together the ultimate work on immutable data structures. I have plans to add immutable collections to D containers once I sort out the allocators matter. Unfortunately, I find myself gasping for time so the news that you are working on such are awesome. I suggest you to absorb the approach taken by ranges and (however incomplete it looks at the moment) std.container, and build on such.

Andrei

On Wednesday, 23 May 2012 at 21:13:48 UTC, Andrei Alexandrescu wrote:
> Okasaki put together the ultimate work on immutable data structures. I have plans to add immutable collections to D containers once I sort out the allocators matter. Unfortunately, I find myself gasping for time so the news that you are working on such are awesome. I suggest you to absorb the approach taken by ranges and (however incomplete it looks at the moment) std.container, and build on such.
>
> Andrei

I would appreciate critics and feedback once I start. The most difficult part is conceptual. Range primitives don't fit. I'm trying to invent something as good as ranges are for mutable data, but I don't feel that I'm qualified enough to get it right without help.

The end goal is to have something as easy to work with as collections of Scala or F# (I don't know Haskell), and, of course, efficient.

On Wednesday, 23 May 2012 at 19:51:02 UTC, Steven Schveighoffer wrote:
> If you need a sorted tree structure that supports sharing immutable state, you likely have to find a different algorithm than redblack, since adding nodes can modify the tree structure via rotates.
>
> -Steve

I don't need to invent here, and it is definitely feasible. Okasaki provided efficient algorithm for inserting nodes, and, IIRC, rotations (not for deleting, though). But OCaml doesn't map to D easily (neither does Haskel, I think).

A side note, I've learned D and switched to Linux in February '12, so I struggle with newbie problems regularly...

On Wednesday, 23 May 2012 at 21:12:04 UTC, Jonathan M Davis wrote:
> 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

I expect problems with eliminating tail calls (especially for mutually recursive functions), but cannot find any other reason, theoretical or implementation, that would necessarily make it execute slowly in D. I think that cache friendliness is possible to achieve, at least in my use cases. What else could go wrong?

On 5/23/12 1:54 PM, David Nadlinger wrote:
> 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.

Yah, FP doesn't like arrays and immutable containers essentially eschew arrays altogether. (The most surprising thing to me is that the FP community generally fails to acknowledge that as a problem.)

Immutable data structures use trees pervasively for random-access data.


Andrei