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 LAA13380; Fri, 9 May 2003 11:53:01 +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 LAA12937 for <caml-list@pauillac.inria.fr>; Fri, 9 May 2003 11:52:59 +0200 (MET DST)
X-SPAM-Warning: Sending machine is listed in blackholes.five-ten-sg.com
Received: from smtp12.cp.tin.it ([212.216.176.206])
	by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h499qwT06876
	for <caml-list@inria.fr>; Fri, 9 May 2003 11:52:59 +0200 (MET DST)
Received: from host119-40.pool212171.interbusiness.it (212.171.40.119) by smtp12.cp.tin.it (6.7.016)
        id 3E8423B100C9772E for caml-list@inria.fr; Fri, 9 May 2003 11:52:57 +0200
From: Stalkern 2 <stalkern2@tin.it>
Reply-To: stalkern2@tin.it
To: caml-list@inria.fr
Subject: [Caml-list] tree walking with... specular rec functions? what else?
Date: Fri, 9 May 2003 11:56:47 +0200
User-Agent: KMail/1.5.1
MIME-Version: 1.0
Content-Type: text/plain;
  charset="us-ascii"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Message-Id: <200305091156.47892.stalkern2@tin.it>
X-Spam: no; 0.00; stalkern:01 downwards:01 clumsy:01 ernesto:01 compiler:01 ocaml:01 afaik:01 rec:01 match:02 tree:02 string:03 directions:96 tail:03 let:04 leaf:04 
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

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.

I've written a rec function containing a specular copy of itself, and have 
each one call each other. 

However, I find this clumsy. 
More exactly:
	1) I don't know what is generally used to walk trees. What's it?
	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?
	3) How comes it that I rewrite the code just to have the compiler accept the 
first interlaced call? What Ocaml feature did I miss?


Code is pasted below; thank you for any hint or opinion on the matter

Ernesto

---------------------------------------------------------------------------------------------------------

type treeLeafType = TreeLeafTypeBuild of (string)
and treeNodeType = TreeNodeTypeBuild of (string * (treeLeafType list) * 	
(treeNodeType list));;

let harvest_nodeNames (aRootNode : treeNodeType)  =
  
  let TreeNodeTypeBuild 
(aRootNodeName,aRootChildrenLeavesList,aRootChildrenNodesList) = aRootNode in

  let rec extract_half_nn  (aTreeNodesList : treeNodeType list) 
aHalfAccumRList =
    match aTreeNodesList with
      [] -> aHalfAccumRList
    | hd::tail -> 
	let TreeNodeTypeBuild 
(aTreeNodeName,aHalfChildrenLeavesList,aHalfChildrenNodesList) = hd in


	let rec extract_flah_nn (aFlahTreeNodesList : treeNodeType list) 
aFlahAccumRList =
	  match aFlahTreeNodesList with
	    [] -> aFlahAccumRList
	  | dh::liat -> 
	      let TreeNodeTypeBuild 
(aFlahNodeName,aFlahChildrenLeavesList,aFlahChildrenNodesList) = dh in
	      
	      let pawsChildrenNamesRL = extract_half_nn aFlahChildrenNodesList []  in
	      extract_flah_nn liat ((aFlahNodeName^" harvested By 
Flah")::(pawsChildrenNamesRL@aFlahAccumRList))
	in

	let swapChildrenNamesRL = extract_flah_nn aHalfChildrenNodesList [] in
	extract_half_nn tail ((aTreeNodeName^" harvested By 
Half")::(swapChildrenNamesRL@aHalfAccumRList)) in

  extract_half_nn [aRootNode] [] ;;


---------------------------------------------------------------------------------------------------------
In practice this gives:
---------------------------------------------------------------------------------------------------------

let aTestTree = TreeNodeTypeBuild
    ("testTree0",
     [TreeLeafTypeBuild "leaf00";
      TreeLeafTypeBuild "leaf01"],
     [TreeNodeTypeBuild
	("subtree03",
	 [TreeLeafTypeBuild "leaf030";
	  TreeLeafTypeBuild "leaf031"],
	 [TreeNodeTypeBuild 
	    ("subtree032", 
	     [], 
	     [])
	]);
      TreeNodeTypeBuild 
	("subtree04", 
	 [], 
	 [TreeNodeTypeBuild
	    ("subtree040",
	     [TreeLeafTypeBuild "leaf0400";
	      TreeLeafTypeBuild "leaf0401"],
	     [TreeNodeTypeBuild 
		("subtree0402", 
		 [], 
		 [])
	    ])
	])]);;

# harvest_nodeNames aTestTree;;
- : string list =
["testTree0 harvested By Half"; "subtree04 harvested By Flah";
 "subtree040 harvested By Half"; "subtree0402 harvested By Flah";
 "subtree03 harvested By Flah"; "subtree032 harvested By Half"]


---------------------------------------------------------------------------------------------------------

-------------------
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