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

[Richard A. O'Keefe]

Bob McKay <bob_mckay at mac.com> (really <rim at cs.adfa.edu.au>) wrote:
	.I'd like to be able to write some generic tree manipulation
		predicates, such as count_nodes(T,N), which would be passed
		an instantiated tree T, and would return the number of nodes.
		And I need it to be determinate. This is straightforward if I
		know the set of functors, but I want this to be part of a library
		for a GP system, so the set of functors won't be known until the
		time that a particular problem is being defined. Is there a
		straightforward way to do this? The way I can half-see, defining
		a higher-order predicate and passing it a list of allowed
		functors, looks a bit scary...
	
It's a lot simpler than that.
Here it is in Haskell syntax.

    count_nodes :: (x -> [x]) -> x -> Int
    count_nodes kids node = 1 + sum (map (count_nodes kids) (kids node))

The function kids takes a node and returns a list of children.
For example:

data Expr
   = Var String
   | Num Double
   | Sum Expr Expr
   | Difference Expr Expr
   | Product Expr Expr
   | Quotient Expr Expr

expr_kids (Var _)	     = []
expr_kids (Num _)	     = []
expr_kids (Sum e1 e2)	     = [e1,e2]
expr_kids (Difference e1 e2) = [e1,e2]
expr_kids (Product e1 e2)    = [e1,e2]
expr_kids (Quotient e1 e2)   = [e1,e2]

count_expr_nodes expr = count_nodes expr_kids expr

One can define a mapping function like this:

    tmap :: (x -> a) -> (a -> [a] -> a) -> (x -> [x]) -> x -> a
    tmap nodeval rebuild kids node =
        rebuild (nodeval node) (map (tmap kids nodeval rebuild) (kids node))

For example, to find the set of variables in an expression:

    expr_vars :: Expr -> [String]
    expr_vars = tmap expr_node_vars (foldl union) expr_kids 

And of course count_nodes is like this:

    count_nodes = tmap (\_ -> 1) (\n ks -> n + sum ks)

Are there any operations you want to provide that are not instances of tmap?
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------