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

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

[Stalkern 2]

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

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

[Brian Hurt]

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

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

[John Carr]

I have a minor comment unrelated to the basic algorithm.

>     ...
>     let rec outer lst =
>         if (List.length lst) == 0 then ()
>         else outer (inner lst [])
>     in
>     ...

In general it is better to test for empty rather than compare the size
of a collection to 0.  With some collections (including lists) testing
for empty takes constant time but computing size takes linear time.

Instead of

	if (List.length lst) == 0 then empty-code else full-code

either of these will be faster:

	if lst == [] then empty-code else full-code

	(match lst with [] -> empty-code | _ -> full-code)

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

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

[Michal Moskal]

On Mon, May 12, 2003 at 08:57:05AM -0400, John Carr wrote:
> 
> I have a minor comment unrelated to the basic algorithm.
> 
> >     ...
> >     let rec outer lst =
> >         if (List.length lst) == 0 then ()
> >         else outer (inner lst [])
> >     in
> >     ...
> 
> In general it is better to test for empty rather than compare the size
> of a collection to 0.  With some collections (including lists) testing
> for empty takes constant time but computing size takes linear time.
> 
> Instead of
> 
> 	if (List.length lst) == 0 then empty-code else full-code
> 
> either of these will be faster:
> 
> 	if lst == [] then empty-code else full-code

    On non-mutable structures, the behavior of (==) is
    implementation-dependent.

Which means that lst = [] does not imply lst == [].

In other words, one should use:

 	if lst = [] then empty-code else full-code

or pattern matching, as you said.

-- 
: Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::::: Wroclaw University, CS Dept : {E-,w}-- {b++,e}>+++ h

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

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

[David Brown]

On Mon, May 12, 2003 at 03:35:42PM +0200, Michal Moskal wrote:

>     On non-mutable structures, the behavior of (==) is
>     implementation-dependent.
> 
> Which means that lst = [] does not imply lst == [].
> 
> In other words, one should use:
> 
>  	if lst = [] then empty-code else full-code
> 
> or pattern matching, as you said.

Is it really not defined by Ocaml?  Ocaml implements the empty list as
the integer value zero.  Although (==) won't tell you if two cons-cells
have the same contents, it will tell you if they are the same.

So is there any implementation of a caml language where [] == [] isn't
always true, for any way that [] is generated?

The (=) has more overhead, and in this case, I'm not sure it is
necessary.

Dave

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

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

[Xavier Leroy]

> > Which means that lst = [] does not imply lst == [].
> > 
> > In other words, one should use:
> > 
> >  	if lst = [] then empty-code else full-code
> > 
> > or pattern matching, as you said.
> 
> Is it really not defined by Ocaml?  Ocaml implements the empty list as
> the integer value zero.  Although (==) won't tell you if two cons-cells
> have the same contents, it will tell you if they are the same.

It happens to work in this case, but relies on features of the
implementation.  It's better to use "==" only between mutable data
structures, where it has a well-defined meaning (two mutable
structures are == iff an in-place modification to one of them affects
the other one as well), and "=" otherwise.

> So is there any implementation of a caml language where [] == [] isn't
> always true, for any way that [] is generated?

Both Caml Light and OCaml ensure [] == [], but again it's better not
to rely on this fact.

> The (=) has more overhead

It doesn't: the OCaml compiler is clever enough to compile "lst = []"
as a direct comparison against the integer value zero.

- Xavier Leroy

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

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

[Xavier Leroy]

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

That sounds like a job for Gérard Huet's "zippers":

G. Huet. The Zipper. Journal of Functional Programming, 7 (5), Sept
1997, pp. 549--554.

Apparently, the paper isn't freely available on-line, but see

http://www.informatik.uni-bonn.de/~ralf/publications/TheWeb.ps.gz

for a quick overview of the zipper, and more advanced stuff.

- Xavier Leroy

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

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

[Stalkern 2]

Il  Sunday 11 May 2003 18:02, Xavier Leroy ha scritto:
> > 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.
>
> That sounds like a job for Gérard Huet's "zippers":
>
> G. Huet. The Zipper. Journal of Functional Programming, 7 (5), Sept
> 1997, pp. 549--554.
>
> Apparently, the paper isn't freely available on-line, but see
>
> http://www.informatik.uni-bonn.de/~ralf/publications/TheWeb.ps.gz
>
> for a quick overview of the zipper, and more advanced stuff.
>

Thank you very much. I'm now using also a posting about zippers on this list 
http://caml.inria.fr/archives/200304/msg00202.html and I was suggested to 
take a look at http://pauillac.inria.fr/~remy/cours/appsem/ocaml-ml.html

Thank you

Ernesto Torresin

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

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

[Gérard Huet]

Le lundi, 12 mai 2003, à 08:55 Europe/Paris, Stalkern 2 a écrit :

> Il  Sunday 11 May 2003 18:02, Xavier Leroy ha scritto:
>>> 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.
>>
>> That sounds like a job for Gérard Huet's "zippers":
>>
>> G. Huet. The Zipper. Journal of Functional Programming, 7 (5), Sept
>> 1997, pp. 549--554.
>>
>> Apparently, the paper isn't freely available on-line, but see
>>
>> http://www.informatik.uni-bonn.de/~ralf/publications/TheWeb.ps.gz
>>
>> for a quick overview of the zipper, and more advanced stuff.
>>
>
> Thank you very much. I'm now using also a posting about zippers on 
> this list
> http://caml.inria.fr/archives/200304/msg00202.html and I was suggested 
> to
> take a look at 
> http://pauillac.inria.fr/~remy/cours/appsem/ocaml-ml.html
>

Hello
My original zipper paper is not on-line, but my latest thoughts on the 
subject are given in
"Linear Contexts and the Sharing Functor: Techniques for Symbolic 
Computation", available from
http://pauillac.inria.fr/~huet/PUBLIC/DB.pdf
Gerard

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