1 -----------------------------------------------------------------------------
4 -- Copyright : (c) The University of Glasgow 2002
5 -- License : BSD-style (see the file libraries/base/LICENSE)
7 -- Maintainer : libraries@haskell.org
8 -- Stability : experimental
9 -- Portability : portable
11 -- Multi-way trees (/aka/ rose trees) and forests.
13 -- Also included are neat presentations for trees and forests.
15 -----------------------------------------------------------------------------
22 -- | Multi-way trees, also known as /rose trees/.
23 data Tree a = Node a (Forest a) -- ^ a value and zero or more child trees.
24 type Forest a = [Tree a]
26 instance Functor Tree where
29 mapTree :: (a -> b) -> (Tree a -> Tree b)
30 mapTree f (Node x ts) = Node (f x) (map (mapTree f) ts)
32 -- explicit instance for Haddock's benefit
33 instance Eq a => Eq (Tree a) where
34 Node x ts == Node x' ts' = x == x' && ts == ts'
36 instance Show a => Show (Tree a) where
38 showList ts s = showForest ts ++ s
40 showTree :: Show a => Tree a -> String
41 showTree = drawTree . mapTree show
43 showForest :: Show a => Forest a -> String
44 showForest = unlines . map showTree
46 drawTree :: Tree String -> String
47 drawTree = unlines . draw
49 draw :: Tree String -> [String]
50 draw (Node x ts0) = grp this (space (length this)) (stLoop ts0)
51 where this = s1 ++ x ++ " "
53 space n = replicate n ' '
56 stLoop [t] = grp s2 " " (draw t)
57 stLoop (t:ts) = grp s3 s4 (draw t) ++ [s4] ++ rsLoop ts
59 rsLoop [] = error "rsLoop:Unexpected empty list."
60 rsLoop [t] = grp s5 " " (draw t)
61 rsLoop (t:ts) = grp s6 s4 (draw t) ++ [s4] ++ rsLoop ts
63 grp fst0 rst = zipWith (++) (fst0:repeat rst)
65 [s1,s2,s3,s4,s5,s6] = ["- ", "--", "-+", " |", " `", " +"]
67 -- | The elements of a tree in pre-order.
68 flatten :: Tree a -> [a]
69 flatten t = squish t []
70 where squish (Node x ts) xs = x:foldr squish xs ts
72 -- | Lists of nodes at each level of the tree.
73 levels :: Tree a -> [[a]]
74 levels t = map (map root) $ takeWhile (not . null) $ iterate subforest [t]
75 where root (Node x _) = x
76 subforest f = [t | Node _ ts <- f, t <- ts]