[Caml-list] Creating a tree type

[Caml-list] Creating a tree type

[Jonathan Roewen]

Hi,

What would be the best approach to creating a tree type such that at
each node, it has some sort of reference to the parent node? Is this
an example of when ocaml's OO side would be more useful?

Basically, I'm creating a UI for my OS; since events will typically
bubble from leaf nodes up through their ancestors until either the
event has been handled or have reached the root node, being able to
reference the parent node efficiently (and easily) is a requirement.

I've tried a recursive type, but both the defintion and code to make
use of it is damn ugly and complicated--there just has to be a better
way to do this sort of thing nicely in ocaml.

Regards,

Jonathan Roewen
--
Desert Spring-Time: An OCaml OS -- http://www.purevoid.org/os/progress/

Re: [Caml-list] Creating a tree type

[Richard Jones]

On Tue, Feb 08, 2005 at 12:41:37AM +1300, Jonathan Roewen wrote:
> Hi,
> 
> What would be the best approach to creating a tree type such that at
> each node, it has some sort of reference to the parent node? Is this
> an example of when ocaml's OO side would be more useful?
> 
> Basically, I'm creating a UI for my OS; since events will typically
> bubble from leaf nodes up through their ancestors until either the
> event has been handled or have reached the root node, being able to
> reference the parent node efficiently (and easily) is a requirement.
> 
> I've tried a recursive type, but both the defintion and code to make
> use of it is damn ugly and complicated--there just has to be a better
> way to do this sort of thing nicely in ocaml.

I had a similar problem - threading mail using JWZ's threading
algorithm.  It requires you maintain a tree with pointers to parent
and/or root nodes.  You can find the implementation (not by me, but by
Radu Grigore) in
http://sandbox.merjis.com/_file/cocanwiki-1.3.8.tar.gz , in file
scripts/lib/cocanwiki_mail.ml

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Caml-list] Creating a tree type

[Jonathan Roewen]

On Mon, 7 Feb 2005 16:01:01 +0000, Jon Harrop <jon@jdh30.plus.com> wrote:
> On Monday 07 February 2005 11:41, Jonathan Roewen wrote:
> > What would be the best approach to creating a tree type such that at
> > each node, it has some sort of reference to the parent node...
> 
> Adding references to the parent of each node in a tree makes the data
> structure a graph and not a tree.
> 
> This can be implemented in several ways. However, I strongly recommend that
> you do not do this to begin with, for several reasons:

Okay, so I realised I could just use a Stack to track a walk through the tree...

A couple more questions though:

1. For the Stack, when I put something in it, is it copied or what?
How does that work?

2. How do I make my tree like a hashtable, i.e. modifications are done
in-place? Some sort of nested Map or something? Using lists to build
up the tree would cause pain when wanting to modify it. It would also
seem inefficient to use lists for this particular use case.

Regards,

Jonathan.

Re: [Caml-list] Creating a tree type

[Pierre Casteran]

Hello,

Did you look at Huet's zippers ?

http://caml.inria.fr/archives/200304/msg00202.html

Pierre


Selon Jonathan Roewen <jonathan.roewen@gmail.com>:

> On Mon, 7 Feb 2005 16:01:01 +0000, Jon Harrop <jon@jdh30.plus.com> wrote:
> > On Monday 07 February 2005 11:41, Jonathan Roewen wrote:
> > > What would be the best approach to creating a tree type such that at
> > > each node, it has some sort of reference to the parent node...
> >
> > Adding references to the parent of each node in a tree makes the data
> > structure a graph and not a tree.
> >
> > This can be implemented in several ways. However, I strongly recommend that
> > you do not do this to begin with, for several reasons:
>
> Okay, so I realised I could just use a Stack to track a walk through the
> tree...
>
> A couple more questions though:
>
> 1. For the Stack, when I put something in it, is it copied or what?
> How does that work?
>
> 2. How do I make my tree like a hashtable, i.e. modifications are done
> in-place? Some sort of nested Map or something? Using lists to build
> up the tree would cause pain when wanting to modify it. It would also
> seem inefficient to use lists for this particular use case.
>
> Regards,
>
> Jonathan.
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>


-- 
Pierre Casteran
(+33) 540006931

----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.