-- 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)