[Caml-list] tree walking with... specular rec functions? what else?

[Stalkern 2 <stalkern2@tin.it>]

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