Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] tree walking with... specular rec functions? what else?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2003-05-09 (09:53)
From: Stalkern 2 <stalkern2@t...>
Subject: [Caml-list] tree walking with... specular rec functions? what else?
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



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 

	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
     [TreeLeafTypeBuild "leaf00";
      TreeLeafTypeBuild "leaf01"],
	 [TreeLeafTypeBuild "leaf030";
	  TreeLeafTypeBuild "leaf031"],
	     [TreeLeafTypeBuild "leaf0400";
	      TreeLeafTypeBuild "leaf0401"],

# 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 Archives:
Bug reports: FAQ:
Beginner's list: