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

[Richard A. O'Keefe]

	I ended up going with Richard's tmap function, partly because I'm
	going to be doing other tree manipulation processes and it seemed
	like a nicely general way of doing things (but I should have known,
	Richard, that what you call 'simpler' is probably going to be a few
	hours of hard thinking...)

The idea comes straight out of the Bird-Meertens stuff.
I'm afraid that some of the more advanced anamorphism/catamorphism has
my head spinning, but I shall never forget the titles of one paper about
this stuff: "Bananas in space".  (The Bananas are of course banana Brackets,
not Australia's best-loved Bananas in Pyjamas.  I once named two virtual
machines B1 and B2, but for some reason they never caught on...)

	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
	
There are many approaches to Genetic Programming.  (For some reason,
our library decided to shelve the journal of evolutionary programming in
the biology section, so I only recently discovered that we had it.  There
is some _great_ stuff there.)  There's the "typeless" approach where you
may replace any subtree (including a leaf) with any other subtree.  But
there is also a "typed" approach, where you may only replace a subtree
with another subtree of the same type.  The typed version has many
advantages.  It can as it were abort non-viable trees before they are
conceived.

tmap uses a 'family' function :: x -> [x].
This operation needs a 'new family' function :: x -> [x] -> x.

Let's do general tree selection and replacement.
Haskell's !! operation is 0-origin; I want 1-origion.

    tselect :: (x -> [x]) -> [Int] -> x -> x
 -- tselect family_function path_to_node top_node -> result
    tselect _ []     node = node
    tselect f (p:ps) node = tselect ps (f node !! p-1)

    treplace :: (x -> [x] -> x) -> (x -> [x]) -> [Int] -> x -> x -> x
 -- treplace new_family_function family_function path_to_node top_node
 --     replacement_node -> result
    treplace _ _ []     _    r = r
    treplace n f (p:ps) node r = n node new_kids
      where new_kids = take (p-1) old_kids ++
                       treplace n f ps (old_kids !! p-1) :
                       drop p old_kids
            old_kids = f node

If you really just want to replace something that the top level,

    top_replace :: (x -> [x] -> x) -> (x -> [x]) -> Int -> x -> x -> x
    top_replace n f p node r = n node new_kids
      where new_kids = take (p-1) old_kids ++ r : drop p old_kids
            old_kids = f node

With the same

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

used in my previous message,

new_family v@(Var _)        []      = v
new_family n@(Num _)        []      = n
new_family (Sum        _ _) [e1,e2] = Sum e1 e2
new_family (Difference _ _) [e1,e2] = Difference e1 e2
new_family (Product    _ _) [e1,e2] = Product e1 e2
new_family (Quotient   _ _) [e1,e2] = Quotient e1 e2

There is a generalised function that could be used to implement tselect,
related to 'fold'.  I think for you the key point is not so much
"which higher order functions should I provide" but
"how many different kinds of functions to I need to pass to them?"
That is, what does the _user_ of this module have to provide?
If the user has to provide lots of different functions,
or if the user has to pass many functions to one of your functions,
that's bad.  If the user only has to write a few simple functions
and not pass very many of them, that's good.

The other day, we found that the 'family' function could do a lot.
Today, we found that the 'new_family' function can do some more.
That's not a lot.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------