From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <jonathan.roewen@gmail.com>
Delivered-To: caml-list@yquem.inria.fr
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39])
	by yquem.inria.fr (Postfix) with ESMTP id D73EFBC88
	for <caml-list@yquem.inria.fr>; Wed,  9 Feb 2005 05:28:33 +0100 (CET)
Received: from rproxy.gmail.com (rproxy.gmail.com [64.233.170.200])
	by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j194SXjC030087
	for <caml-list@yquem.inria.fr>; Wed, 9 Feb 2005 05:28:33 +0100
Received: by rproxy.gmail.com with SMTP id i8so1147880rne
        for <caml-list@yquem.inria.fr>; Tue, 08 Feb 2005 20:28:32 -0800 (PST)
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws;
        s=beta; d=gmail.com;
        h=received:message-id:date:from:reply-to:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:references;
        b=UOtzH3xsaEkwbeQmBpa3+NtjqDZivSn76d0iVI0o3PAQNi6uBfyclJE+0p/XWnOSRZXsI33VuU1Y3bJNEtt6JH9Qvq7o9fGHTFyBtIABVy/ElgMKtRgRrzj8AzEJCqPfxd0tfN1+00yC3tASCcUSR5EUjPx8tcVo6e2k/90R6q0=
Received: by 10.38.164.36 with SMTP id m36mr9358rne;
        Tue, 08 Feb 2005 20:28:32 -0800 (PST)
Received: by 10.38.209.53 with HTTP; Tue, 8 Feb 2005 20:28:32 -0800 (PST)
Message-ID: <ad8cfe7e0502082028bd9caeb@mail.gmail.com>
Date: Wed, 9 Feb 2005 17:28:32 +1300
From: Jonathan Roewen <jonathan.roewen@gmail.com>
Reply-To: Jonathan Roewen <jonathan.roewen@gmail.com>
To: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Creating a tree type
In-Reply-To: <200502071601.01981.jon@jdh30.plus.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
References: <ad8cfe7e050207034127df7f73@mail.gmail.com>
	 <200502071601.01981.jon@jdh30.plus.com>
X-Miltered: at concorde with ID 42099171.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Spam: no; 0.00; caml-list:01 wrote:01 wrote:01 stack:01 stack:01 hashtable:01 ...:98 ...:98 node:01 node:01 inefficient:01 graph:01 data:02 tree:02 tree:02 
X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr
X-Spam-Status: No, score=0.0 required=5.0 tests=RCVD_BY_IP autolearn=disabled 
	version=3.0.2
X-Spam-Level: 

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.