-- Code from Section 3.4
module Trees where
import Lists
data Rose a = Node a (Forest a)
type Forest a = List (Rose a)
foldR :: (a -> c -> b) -> (List b -> c) -> Rose a -> b
foldR f g (Node a ts) = f a (foldF f g ts)
foldF :: (a -> c -> b) -> (List b -> c) -> Forest a -> c
foldF f g ts = g (mapL (foldR f g) ts)
foldRose :: (a -> List b -> b) -> Rose a -> b
foldRose f (Node a ts) = f a (mapL (foldRose f) ts)
unfoldR :: (b -> a) -> (b -> List b) -> b -> Rose a
unfoldR f g x = Node (f x) (unfoldF f g x)
unfoldF :: (b -> a) -> (b -> List b) -> b -> Forest a
unfoldF f g x = mapL (unfoldR f g) (g x)
root (Node a ts) = a
kids (Node a ts) = ts
dft :: Rose a -> List a
dff :: Forest a -> List a
(dft,dff) = (foldR f g, foldF f g)
where
f = Cons
g = concatL
levelt :: Rose a -> List (List a)
levelf :: Forest a -> List (List a)
(levelt,levelf) = (foldR f g, foldF f g)
where
f x xss = Cons (wrap x) xss
g = foldL (lzw appendL) Nil
lzw :: (a -> a -> a) -> List a -> List a -> List a
lzw f Nil ys = ys
lzw f xs Nil = xs
lzw f (Cons x xs) (Cons y ys) = Cons (f x y) (lzw f xs ys)
bft :: Rose a -> List a
bff :: Forest a -> List a
bft = concatL . levelt
bff = concatL . levelf
levelt' :: Rose a -> List (List a) -> List (List a)
levelt' t = lzw appendL (levelt t)
levelf' :: Forest a -> List (List a) -> List (List a)
levelf' ts = lzw appendL (levelf ts)
bffQueue :: Forest a -> List a
bffQueue = unfoldL nil first rest
where
first (Cons t ts) = root t
rest (Cons t ts) = appendL ts (kids t)