From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id RAA23767; Fri, 9 May 2003 17:12:38 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA23687 for ; Fri, 9 May 2003 17:12:37 +0200 (MET DST) Received: from epexch01.qlogic.org ([63.170.40.3]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h49FCaT20506 for ; Fri, 9 May 2003 17:12:36 +0200 (MET DST) Received: from epmailtmp.qlogic.org ([10.20.33.254]) by epexch01.qlogic.org with Microsoft SMTPSVC(5.0.2195.5329); Fri, 9 May 2003 10:11:21 -0500 Received: from [10.20.33.146] ([10.20.33.146]) by epmailtmp.qlogic.org with Microsoft SMTPSVC(5.0.2195.4905); Fri, 9 May 2003 10:11:21 -0500 Date: Fri, 9 May 2003 10:23:20 -0500 (CDT) From: Brian Hurt X-X-Sender: Reply-To: Brian Hurt To: Stalkern 2 cc: Subject: Re: [Caml-list] tree walking with... specular rec functions? what else? In-Reply-To: <200305091156.47892.stalkern2@tin.it> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-OriginalArrivalTime: 09 May 2003 15:11:21.0276 (UTC) FILETIME=[3F9FCFC0:01C3163D] X-Spam: no; 0.00; qlogic:01 caml-list:01 stalkern:01 downwards:01 recursion:01 leafs:01 accum:01 afaik:01 rec:01 variant:02 nodes:02 binary:02 node:02 match:02 inner:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Fri, 9 May 2003, Stalkern 2 wrote: > Hello to everybody > > I've a simple tree structure and I want to walk it. Since in such a simple > tree structure I can go AFAIK only sidewards or upwards/downwards, and I need > to do both, I guess what can be an efficent way to do so. Recursion is your friend. Let's assume we have a type like: type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree This is the most basic of tree data structures. Data can be held in any node, the bottom of the tree is marked by leafs. We want to define a walk function, which calls a function f on all elements of the tree, in a depth-first pattern. This is simple: let rec walk f tree = match tree with Leaf -> () | Node(data, left, right) -> walk f left; f data; walk f right ;; Obvious variations include which order you evaluate the last three statements as. Equally valid would be: f data; walk f left; walk f right; and walk f left; walk f right; f data; . Doing a breadth first is a little bit more tricky, as you have to keep a list of the next nodes down: let rec walk f tree = let rec inner lst accum = match lst with [] -> List.rev accum | Leaf :: t -> inner t accum | Node(data, left, right) :: t -> f data; inner t (right :: left :: accum) in let rec outer lst = if (List.length lst) == 0 then () else outer (inner lst []) in outer ( [ tree ] ) ;; Basically, I keep a list of the nodes at each level. As I walk the list, calling f on all non-leaf nodes, I create the list of the nodes at the next level down. Note the List.rev trick I pull, to keep the nodes in the "expected" order. > 2) I think that this approach isn't flexible. What if I had a > tree where I can move in other directions as well? Or if I were > dealing with 5-generation grandchildren only? A variant of the breadth-first walking I did above could easily generate a list of all nodes on level 5. Dealing with multiple children is easy. Assume that instead of the binary tree structure we had above, we had an n'ary tree structure, like: type 'a tree = Leaf | Node of 'a * 'a tree list Each node holds data and a list of 0 or more children it has. Depth first search would then become: let rec walk f tree = let rec loop lst = match lst with [] -> () | h :: t -> walk f h ; loop t in match tree with Leaf -> () | Node(data, children) -> f data; loop children ;; A similiar modification works to do breadth first walking. More general data structures aren't really trees anymore, they're graphs. But graph walking works more or less the same way. Hope this helps. Brian ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners