--------------------
-- Tree data type plus convenience functions

data Tree a = Spread a [Tree a]  deriving (Eq,Ord,Read)

top (Spread a _) = a

kids (Spread _ ks) = ks

leaf = flip Spread []


--------------------
-- Some test data

test  = Spread 0 [  Spread 1 [leaf 4, leaf 5],
                    leaf 2,
                    Spread 3 [leaf 6, leaf 7, leaf 8]]

test2 = Spread 1 [	Spread 2 [Spread 6 [leaf 11, leaf 12], leaf 7], 
                	Spread 3 [],
                	Spread 4 [Spread 8 [leaf 13, leaf 14], leaf 9, Spread 10 [leaf 15]]]


--------------------
-- Jeremy Gibbons and Geraint Jones' version of breadth-first traversal

unfold p f g x | p x = []
               | otherwise = f x : unfold p f g (g x)

bft = concat . unfold null (map top) (concat . map kids) . (:[])

-- And the "deforested" version

bfd = bfdef . (:[])

bfdef [] = []
bfdef ts = map top ts ++ bfdef (concat (map kids ts))


instance Show a => Show (Tree a) where
  show = prt ""































--------------------
-- fold and map combinators for Trees

foldm f (Spread a ts) = f a (map (foldm f) ts)

mapm f = foldm (Spread . f)


--------------------
-- Tree printing

prt pref (Spread a ts) = pref ++ unline (show a : map (prt ("  "++pref)) ts)

sh t = putStr (prt "" t)

unline = foldr1 (\x y-> x ++ '\n' : y)