(no subject)

[Scott Turner]

On Sunday 19 August 2001 05:41, you wrote:
> Does anyone know how to replace
> or take out a node from a tree structure ? 

Using Haskell, the way we deal with trees is usually rather different
from what is done in C or Lisp.  Suppose you're dealing with a 
typical tree in Haskell, defined something like
    data Tree = Branch Tree Tree | Leaf String
An example of a tree structure would be
    a_tree = Branch (Leaf "x") (Branch (Leaf "x") (Leaf "y"))

The usual thing is to define a function which performs
the desired replacement, for example
    replace_first_branch :: Tree -> Tree -> Tree
    replace_first_branch tree_in new_branch = tree_out
      where
        Branch first_branch second_branch = tree_in
        tree_out = Branch new_branch second_branch
or
    replace_first_leaf :: Tree -> Tree -> Tree
    replace_first_leaf tree_in new_branch = r tree_in
      where
	r (Leaf x) = new_branch
	r (Branch x y) = Branch (r x) y

The above defines a "pure" function, without side effects.  The function 
returns a new tree structure and the input structure is unchanged.  But it 
sounds as if you intend to modify an existing structure.  For this purpose 
you need a structure with modifiable nodes.  

    import IOExts
    import Monad

    type TreeRef = IORef Tree
    data Tree = Branch TreeRef TreeRef | Leaf String

    replaceFirstLeaf r t = do Branch r1 r2 <- readIORef r
			      is_leaf <- testLeaf r1
			      when is_leaf (writeIORef r (Branch t r2))
    testLeaf r = do v <- readIORef r
		    return $ case v of Leaf x    -> True
				       otherwise -> False

The above code uses Hugs extensions for modifiable references, i.e. the IORef 
type, with functions readIORef and writeIORef.  Most Haskell implementations 
support an extension of this kind.