[mercury-users] Help: generic tree predicates; modules

[Ralph Becket]

Bob McKay, Thursday,  9 May 2002:
> 
> So on to the next challenge, which is to plug a newly generated
> subtree in a specific (randomly generated) position (the numeric
> position in an infix traversal) in an existing tree (I'm being
> careless with my phrasing, but you know what I mean):
> 
> insert:: Exp,int,Exp -> Exp

If I understand you correctly, you want to (a) define a mapping from
the integers to nodes in a tree and (b) have a function that will
replace a node with a given index with a different subtree.

To do this, you're going to need a function that will allow you to
replace a given child of a node.  This will have to be specific to
each tree type.

It may well be easier to use a generic tree type rather than try to
generalise over them by passing higher order functions.  One candidate
type is

	:- type tree(T) ---> tree(T, list(tree(T))).

One way to index the nodes is in depth-first traversal order.  If you
annotate each subtree with its size, the code is simplified (you can
avoid the annotation if you don't mind more expensive indexing):

	:- type tree(T) --->
		tree(T, int, trees(T)).

	:- type trees(T) == list(tree(T)).

	:- func sz(tree(T)) = int.

	sz(tree(_, Sz, _)) = Sz.

Now we can write 

	:- func replace(tree(T), int, tree(T)) = tree(T).

	replace(tree(X, _, Ts0), N, R) = T :-
		( if N =< 0 then
			T  = R
		  else
		  	Ts = replace_child(Ts0, N - 1, R),
			Sz = sum(map(sz, Ts)),
			T  = tree(X, Sz, Ts)
		).

	:- func replace_child(trees(T), int, tree(T)) = trees(T).

	replace_child([],       _, _) = [].

	replace_child([T | Ts], N, R) =
		( if N < sz(T) then [replace(T, N, R) | Ts]
		               else [T | replace_child(Ts, N - sz(T), R)]
		).

The transformation from this code to generic stuff using higher order
functions to extract and replace child nodes is straightforward, but
not pretty.

(If you want to squeeze a little more efficiency out of the above,
change replace_child/3 into a predicate that computes not only the
replacement children, but also the change in size due to the
replacement.  You can then avoid the sum(map(sz, Ts)) in replace/3.
Although it may well not be worth it.)

- Ralph
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------