# (no subject)

**Scott Turner
**
p.turner@computer.org

*Sun, 19 Aug 2001 09:08:33 -0500*

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.