Trees

Module Tree defines several general-purpose functions for operating on trees.

treeRoot    	:: Tree a -> a
treeChildren	:: Tree a -> [Tree a]
preorderTree :: Tree a -> [a]

treeRoot and treeChildren are the projection functions, returning the root value and list of subtrees respectively. preorderTree returns a list of all values stored in the tree.

The usual polytypic functions are available, which do the obvious things:

mapTree :: (a -> b) -> Tree a -> Tree b
cataTree :: ((a, [b]) -> b) -> Tree a -> b
anaTree  :: (b -> (a, [b])) -> b -> Tree a
instance Functor Tree where fmap = mapTree

foldTree is the Tree analogue of the list function foldr. accumTree is a shape-preserving downwards accumulation; it takes a seed value and a combining function f :: a -> b -> (c,a), which it evaluates at each level of the tree to produce a new node value and seed. scanTree is a variant of accumTree; it's analogous to the list function scanl.

foldTree :: (a -> b -> c) -> (c -> b -> b) -> b -> Tree a -> c
scanTree :: (a -> b -> a) -> a -> Tree b -> Tree a
accumTree :: (a -> b -> (c, a)) -> a -> Tree b -> Tree c

foldTree tree cons nil (Tree a c)
	= tree a (foldr cons nil (map (foldTree tree cons nil) c))
scanTree op a (Tree b children)
	= let a' = a `op` b in Tree a' (map (scanTree op a') children)
accumTree op a (Tree b children)
	= let (c,a') = a `op` b in Tree c (map (accumTree op a') children)