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