{----------------------------------------------------------------------------

	Transformation und Faltung von allgemeinen Baeumen (Rose Trees)

----------------------------------------------------------------------------}

data Rose a = Node a [Rose a]
		deriving Show
		
-- map und fold 
mapRose :: (a -> b) -> Rose a -> Rose b
mapRose f (Node x ts) 
	=  Node (f x) (map (mapRose f) ts)
	
foldRose :: (a -> [b] -> b) -> Rose a -> b
foldRose f (Node x ts)
	 =  f x (map (foldRose f) ts)
	 

-- einfache Anwendungen

-- Aufsummieren aller Baumeintraege
sumRose :: Num a => Rose a -> a
sumRose = foldRose (flip ((+).sum))

-- Bestimmung der Knotenzahl
sizeRose :: Rose a -> Int
sizeRose =  foldRose (\ _ ns -> 1 + sum ns)

-- mapRose als Instanz von foldRose
mapRose'   :: (a -> b) -> Rose a -> Rose b
mapRose' f =  foldRose (Node . f)


-- Beispielbaum
baum = Node 1 [ Node 2 [], 
		Node 3 [Node 6 [], 
			Node 7 [], 
			Node 8 []
			],
		Node 4 [], 
		Node 5 []
		]