Stax: immutable TreeSet?

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Stax: immutable TreeSet?

interaction-designer
Hi List,

Would you like to have an immutable TreeSet in Stax? I am making one now. Would it be a nice contribution to Stax?

Greetings, Simon

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Stax: immutable TreeSet?

John A. De Goes

Would _love_ an immutable TreeSet!

You can get the ordering from Stax.getOrderFor([type]), which will return a function that compares 'a' and 'b'.

TreeSets can have more efficient immutable implementation than HashSets. If nodes point only to their children, then if a node changes, only the nodes from that node to the top have to change. If nodes point only to their parents, then you get even more localization (although many operations become more difficult, with more book keeping required).

Regards,

John A. De Goes
Twitter: @jdegoes
LinkedIn: http://linkedin.com/in/jdegoes

On Sep 24, 2010, at 1:13 AM, [hidden email] wrote:

> Hi List,
>
> Would you like to have an immutable TreeSet in Stax? I am making one now. Would it be a nice contribution to Stax?
>
> Greetings, Simon
>
> --
> haXe - an open source web programming language
> http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Stax: immutable TreeSet?

interaction-designer
John, others

And how about an immutable tree, would that be a nice contribution to Stax as well?

Greetings, Simon


----- Oorspronkelijk bericht -----
Van: "John A. De Goes" <[hidden email]>
Aan: "The haXe compiler list" <[hidden email]>
Verzonden: Vrijdag 24 september 2010 17:27:43 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
Onderwerp: Re: [haXe] Stax: immutable TreeSet?


Would _love_ an immutable TreeSet!

You can get the ordering from Stax.getOrderFor([type]), which will return a function that compares 'a' and 'b'.

TreeSets can have more efficient immutable implementation than HashSets. If nodes point only to their children, then if a node changes, only the nodes from that node to the top have to change. If nodes point only to their parents, then you get even more localization (although many operations become more difficult, with more book keeping required).

Regards,

John A. De Goes
Twitter: @jdegoes
LinkedIn: http://linkedin.com/in/jdegoes

On Sep 24, 2010, at 1:13 AM, [hidden email] wrote:

> Hi List,
>
> Would you like to have an immutable TreeSet in Stax? I am making one now. Would it be a nice contribution to Stax?
>
> Greetings, Simon
>
> --
> haXe - an open source web programming language
> http://haxe.org


--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Stax: immutable TreeSet?

John A. De Goes

That would be fantastic! Tree is a special kind of graph (directed acyclic graph). Much research has been spent devising ways to make immutable implementations efficient. I recommend searching for Haskell implementations/papers to gain some idea of how to create a high-performance immutable implementation, which shares a generalized graph interface for future graph types.

Regards,

John A. De Goes
Twitter: @jdegoes
LinkedIn: http://linkedin.com/in/jdegoes

On Sep 24, 2010, at 1:26 PM, [hidden email] wrote:

> John, others
>
> And how about an immutable tree, would that be a nice contribution to Stax as well?
>
> Greetings, Simon
>
>
> ----- Oorspronkelijk bericht -----
> Van: "John A. De Goes" <[hidden email]>
> Aan: "The haXe compiler list" <[hidden email]>
> Verzonden: Vrijdag 24 september 2010 17:27:43 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
> Onderwerp: Re: [haXe] Stax: immutable TreeSet?
>
>
> Would _love_ an immutable TreeSet!
>
> You can get the ordering from Stax.getOrderFor([type]), which will return a function that compares 'a' and 'b'.
>
> TreeSets can have more efficient immutable implementation than HashSets. If nodes point only to their children, then if a node changes, only the nodes from that node to the top have to change. If nodes point only to their parents, then you get even more localization (although many operations become more difficult, with more book keeping required).
>
> Regards,
>
> John A. De Goes
> Twitter: @jdegoes
> LinkedIn: http://linkedin.com/in/jdegoes
>
> On Sep 24, 2010, at 1:13 AM, [hidden email] wrote:
>
>> Hi List,
>>
>> Would you like to have an immutable TreeSet in Stax? I am making one now. Would it be a nice contribution to Stax?
>>
>> Greetings, Simon
>>
>> --
>> haXe - an open source web programming language
>> http://haxe.org
>
>
> --
> haXe - an open source web programming language
> http://haxe.org
>
> --
> haXe - an open source web programming language
> http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Stax: immutable TreeSet?

interaction-designer
In reply to this post by interaction-designer
Hi John,

First, why is it so hard to find a efficient immutable multi-way Tree (rose tree) ?
Is it because some operations need some GC?

What are the pros and cons of a mutable tree with a functional interface vs a pure functional tree?
What are your thoughts about this haskell implementation of a rose tree?

Is a purely functional approach feasible? First order logic can be used in very advanced ways (formal verification, just to mention one). I am just an interaction designer ( usability, user experience design, graphics design). I design to much for a coder and I code to much for a designer. I  am crossing a gap which is quite large (which makes it interesting). I am not at all educated in CS nor in Math. I have a Master of Arts in Interactive Media. So if it's too hard for me (which it probably is, sorry about that ) I 'll go for the simulated one. But would you be happy with such one?

Secondly I might like to implement the TreeSet using a red-black tree (in the spirit of Scala's implementation).
How do you like this haskell implementation of a red-black tree?

Simon

PS: You probably already know of http://www.haskell.org/haskellwiki/Category:Proposals?

----- Oorspronkelijk bericht -----
Van: "John A. De Goes" <[hidden email]>
Aan: "The haXe compiler list" <[hidden email]>
Verzonden: Zaterdag 25 september 2010 22:42:25 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
Onderwerp: Re: [haXe] Stax: immutable TreeSet?


That would be fantastic! Tree is a special kind of graph (directed acyclic graph). Much research has been spent devising ways to make immutable implementations efficient. I recommend searching for Haskell implementations/papers to gain some idea of how to create a high-performance immutable implementation, which shares a generalized graph interface for future graph types.

Regards,

John A. De Goes
Twitter: @jdegoes
LinkedIn: http://linkedin.com/in/jdegoes

On Sep 24, 2010, at 1:26 PM, [hidden email] wrote:

> John, others
>
> And how about an immutable tree, would that be a nice contribution to Stax as well?
>
> Greetings, Simon
>
>
> ----- Oorspronkelijk bericht -----
> Van: "John A. De Goes" <[hidden email]>
> Aan: "The haXe compiler list" <[hidden email]>
> Verzonden: Vrijdag 24 september 2010 17:27:43 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
> Onderwerp: Re: [haXe] Stax: immutable TreeSet?
>
>
> Would _love_ an immutable TreeSet!
>
> You can get the ordering from Stax.getOrderFor([type]), which will return a function that compares 'a' and 'b'.
>
> TreeSets can have more efficient immutable implementation than HashSets. If nodes point only to their children, then if a node changes, only the nodes from that node to the top have to change. If nodes point only to their parents, then you get even more localization (although many operations become more difficult, with more book keeping required).
>
> Regards,
>
> John A. De Goes
> Twitter: @jdegoes
> LinkedIn: http://linkedin.com/in/jdegoes
>
> On Sep 24, 2010, at 1:13 AM, [hidden email] wrote:
>
>> Hi List,
>>
>> Would you like to have an immutable TreeSet in Stax? I am making one now. Would it be a nice contribution to Stax?
>>
>> Greetings, Simon
>>
>> --
>> haXe - an open source web programming language
>> http://haxe.org
>
>
> --
> haXe - an open source web programming language
> http://haxe.org
>
> --
> haXe - an open source web programming language
> http://haxe.org


--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Stax: immutable TreeSet?

John A. De Goes
<base href="x-msg://126/">

I think Stax needs both mutable and immutable interfaces. For graphs, the main problem is constructing it, so the builder pattern can be used (write-only builder, which builds an immutable graph). Graphs in real applications tend to change slowly.

A tree would be a good introduction to the more general concept of a graph. You don't have to start with a fancy implementation. There are two simple approaches you can use:

Node<T>: {
  var children: List<Node>;
  var data: T;
}

and:

Node<T>: {
  var parent: Option<Node>;
  var data: T;
}

If you choose the first one, then modification to any node, will result in that node being replaced, and all its ancestors up to the root being replaced. Now, you can still share some structure at each level: you can keep part of the children list. Let's say you only have "root" node with 10 children, and you add a node at index = 5. Then you can share the sublist at indices 6 - 9. That is,

newRoot.children = oldRoot.children.take(5).concat(oldRoot.children.drop(5).cons(newNode));

Due to the implementation of List, the sublist "oldRoot.children.drop(5)" shares the same structure as "oldRoot.children" (no copying is involved).

So even with the first approach, you can share quite a lot of data.

With the second approach, any modification to a node, will result in all the descendants of the node being replaced (each requires a new parent). I don't know for sure, but I think it will be easier to share more structure with the second approach, but the book-keeping will be messier.

You could also implement a faster version of haxe.data.collections.Set, the Set included with Stax. The implementation is currently based on a hash, and can be improved by using a tree structure, such as a red-black tree. But if you decide to do this, you will be making a faster version of Set, not actually contributing a new kind of collection to Stax (either way, I think it would be useful).

Regards,

John A. De Goes
Twitter: @jdegoes 
LinkedIn: http://linkedin.com/in/jdegoes

On Sep 25, 2010, at 7:15 PM, [hidden email] wrote:

Hi John,

First, why is it so hard to find a efficient immutable multi-way Tree (rose tree) ? 
Is it because some operations need some GC? 

What are the pros and cons of a mutable tree with a functional interface vs a pure functional tree?
What are your thoughts about this haskell implementation of a rose tree?

Is a purely functional approach feasible? First order logic can be used in very advanced ways (formal verification, just to mention one). I am just an interaction designer ( usability, user experience design, graphics design). I design to much for a coder and I code to much for a designer. I  am crossing a gap which is quite large (which makes it interesting). I am not at all educated in CS nor in Math. I have a Master of Arts in Interactive Media. So if it's too hard for me (which it probably is, sorry about that ) I 'll go for the simulated one. But would you be happy with such one? 

Secondly I might like to implement the TreeSet using a red-black tree (in the spirit of Scala's implementation). 
How do you like this haskell implementation of a red-black tree?

Simon

PS: You probably already know of http://www.haskell.org/haskellwiki/Category:Proposals? 

----- Oorspronkelijk bericht -----
Van: "John A. De Goes" <[hidden email]>
Aan: "The haXe compiler list" <[hidden email]>
Verzonden: Zaterdag 25 september 2010 22:42:25 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
Onderwerp: Re: [haXe] Stax: immutable TreeSet?


That would be fantastic! Tree is a special kind of graph (directed acyclic graph). Much research has been spent devising ways to make immutable implementations efficient. I recommend searching for Haskell implementations/papers to gain some idea of how to create a high-performance immutable implementation, which shares a generalized graph interface for future graph types.

Regards,

John A. De Goes
Twitter: @jdegoes 
LinkedIn: http://linkedin.com/in/jdegoes

On Sep 24, 2010, at 1:26 PM, [hidden email] wrote:

> John, others
> 
> And how about an immutable tree, would that be a nice contribution to Stax as well?
> 
> Greetings, Simon 
> 
> 
> ----- Oorspronkelijk bericht -----
> Van: "John A. De Goes" <[hidden email]>
> Aan: "The haXe compiler list" <[hidden email]>
> Verzonden: Vrijdag 24 september 2010 17:27:43 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
> Onderwerp: Re: [haXe] Stax: immutable TreeSet?
> 
> 
> Would _love_ an immutable TreeSet!
> 
> You can get the ordering from Stax.getOrderFor([type]), which will return a function that compares 'a' and 'b'.
> 
> TreeSets can have more efficient immutable implementation than HashSets. If nodes point only to their children, then if a node changes, only the nodes from that node to the top have to change. If nodes point only to their parents, then you get even more localization (although many operations become more difficult, with more book keeping required).
> 
> Regards,
> 
> John A. De Goes
> Twitter: @jdegoes 
> LinkedIn: http://linkedin.com/in/jdegoes
> 
> On Sep 24, 2010, at 1:13 AM, [hidden email] wrote:
> 
>> Hi List,
>> 
>> Would you like to have an immutable TreeSet in Stax? I am making one now. Would it be a nice contribution to Stax?
>> 
>> Greetings, Simon
>> 
>> -- 
>> haXe - an open source web programming language
>> http://haxe.org
> 
> 
> --
> haXe - an open source web programming language
> http://haxe.org
> 
> -- 
> haXe - an open source web programming language
> http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
-- 
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Stax: immutable TreeSet?

Simon Asselbergs
Hi I John,

As always thanks for your clear emails (I wish I could be so clear). It's interesting you say Stax needs both mutable and immutable. This thought was going through my head also. I was not familiar with Graphs before you pointed me to them in your previous email. I have investigated a bit, studied JGraphT and  graphocaml. And the paper about graphocaml, is finger licking good.

I have send some emails to some CS people who are deeply into involved in research on Graphs. I also didn't knew before GC needs to be done too. Found some very interesting article on that too (see pdf). I am also very much by the Haskell containers, it's a short paper I simply couldn't resist reading it, maybe you like it also.

Let me try to come up with a fancy graph solution first, if I give up(I won't cross my fingers) I might as well skip the fancy pansy and go to the Trees. Though if no objection, a fancy pansy Graph it is. It's just too much fun, not to do it. Scala has the builder pattern at its core of the collections, btw. I see you often roughly follow Scala's core design.

If you write something about the design of your data collections on the wiki, I will try to build in the same spirit, is that OK?

Cordially, Greetings Simon

On Sat, Oct 2, 2010 at 7:54 PM, John A. De Goes <[hidden email]> wrote:

I think Stax needs both mutable and immutable interfaces. For graphs, the main problem is constructing it, so the builder pattern can be used (write-only builder, which builds an immutable graph). Graphs in real applications tend to change slowly.

A tree would be a good introduction to the more general concept of a graph. You don't have to start with a fancy implementation. There are two simple approaches you can use:

Node<T>: {
  var children: List<Node>;
  var data: T;
}

and:

Node<T>: {
  var parent: Option<Node>;
  var data: T;
}

If you choose the first one, then modification to any node, will result in that node being replaced, and all its ancestors up to the root being replaced. Now, you can still share some structure at each level: you can keep part of the children list. Let's say you only have "root" node with 10 children, and you add a node at index = 5. Then you can share the sublist at indices 6 - 9. That is,

newRoot.children = oldRoot.children.take(5).concat(oldRoot.children.drop(5).cons(newNode));

Due to the implementation of List, the sublist "oldRoot.children.drop(5)" shares the same structure as "oldRoot.children" (no copying is involved).

So even with the first approach, you can share quite a lot of data.

With the second approach, any modification to a node, will result in all the descendants of the node being replaced (each requires a new parent). I don't know for sure, but I think it will be easier to share more structure with the second approach, but the book-keeping will be messier.

You could also implement a faster version of haxe.data.collections.Set, the Set included with Stax. The implementation is currently based on a hash, and can be improved by using a tree structure, such as a red-black tree. But if you decide to do this, you will be making a faster version of Set, not actually contributing a new kind of collection to Stax (either way, I think it would be useful).

Regards,

John A. De Goes
Twitter: @jdegoes 
LinkedIn: http://linkedin.com/in/jdegoes

On Sep 25, 2010, at 7:15 PM, [hidden email] wrote:

Hi John,

First, why is it so hard to find a efficient immutable multi-way Tree (rose tree) ? 
Is it because some operations need some GC? 

What are the pros and cons of a mutable tree with a functional interface vs a pure functional tree?
What are your thoughts about this haskell implementation of a rose tree?

Is a purely functional approach feasible? First order logic can be used in very advanced ways (formal verification, just to mention one). I am just an interaction designer ( usability, user experience design, graphics design). I design to much for a coder and I code to much for a designer. I  am crossing a gap which is quite large (which makes it interesting). I am not at all educated in CS nor in Math. I have a Master of Arts in Interactive Media. So if it's too hard for me (which it probably is, sorry about that ) I 'll go for the simulated one. But would you be happy with such one? 

Secondly I might like to implement the TreeSet using a red-black tree (in the spirit of Scala's implementation). 
How do you like this haskell implementation of a red-black tree?

Simon

PS: You probably already know of http://www.haskell.org/haskellwiki/Category:Proposals? 

----- Oorspronkelijk bericht -----
Van: "John A. De Goes" <[hidden email]>
Aan: "The haXe compiler list" <[hidden email]>
Verzonden: Zaterdag 25 september 2010 22:42:25 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
Onderwerp: Re: [haXe] Stax: immutable TreeSet?


That would be fantastic! Tree is a special kind of graph (directed acyclic graph). Much research has been spent devising ways to make immutable implementations efficient. I recommend searching for Haskell implementations/papers to gain some idea of how to create a high-performance immutable implementation, which shares a generalized graph interface for future graph types.

Regards,

John A. De Goes
Twitter: @jdegoes 
LinkedIn: http://linkedin.com/in/jdegoes

On Sep 24, 2010, at 1:26 PM, [hidden email] wrote:

> John, others
> 
> And how about an immutable tree, would that be a nice contribution to Stax as well?
> 
> Greetings, Simon 
> 
> 
> ----- Oorspronkelijk bericht -----
> Van: "John A. De Goes" <[hidden email]>
> Aan: "The haXe compiler list" <[hidden email]>
> Verzonden: Vrijdag 24 september 2010 17:27:43 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
> Onderwerp: Re: [haXe] Stax: immutable TreeSet?
> 
> 
> Would _love_ an immutable TreeSet!
> 
> You can get the ordering from Stax.getOrderFor([type]), which will return a function that compares 'a' and 'b'.
> 
> TreeSets can have more efficient immutable implementation than HashSets. If nodes point only to their children, then if a node changes, only the nodes from that node to the top have to change. If nodes point only to their parents, then you get even more localization (although many operations become more difficult, with more book keeping required).
> 
> Regards,
> 
> John A. De Goes
> Twitter: @jdegoes 
> LinkedIn: http://linkedin.com/in/jdegoes
> 
> On Sep 24, 2010, at 1:13 AM, [hidden email] wrote:
> 
>> Hi List,
>> 
>> Would you like to have an immutable TreeSet in Stax? I am making one now. Would it be a nice contribution to Stax?
>> 
>> Greetings, Simon
>> 
>> -- 
>> haXe - an open source web programming language
>> http://haxe.org
> 
> 
> --
> haXe - an open source web programming language
> http://haxe.org
> 
> -- 
> haXe - an open source web programming language
> http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
-- 
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org