-- File: GeneralTree.hs
-- Copyright (C) 2010 Gregory D. Weber.
-- General trees using a node with root and list of children.
-- Very similar to Data.Tree, but less powerful.

module GeneralTree
where

import Prelude hiding (fmap)
import Control.Monad (mapM_)

data Tree a = Node a [Tree a]
            deriving (Eq, Read, Show)

treeRoot :: Tree a -> a
treeRoot (Node a _) = a

treeSubtrees :: Tree a -> [Tree a]
treeSubtrees (Node _ subtrees) = subtrees

-- Size (number of nodes in a tree)

size :: Tree a -> Int
size (Node root subtrees) = 1 + sum (map size subtrees)

height :: Tree a -> Int
height (Node root []) = 0
height (Node root subtrees) = 1 + maximum (map height subtrees)


-- Traversal

preorder :: Tree a -> [a]
preorder (Node root subtrees) = root : concatMap preorder subtrees

-- fmapping

fmap :: (a -> b) -> Tree a -> Tree b
fmap f (Node root subtrees) = Node (f root)
                                   (map (fmap f) subtrees)

-- Test tree

t1 :: Tree String
t1 = Node "a" 
          [Node "b" []
          , Node "c" []
          , Node "d"
                 [Node "e" []
                 , Node "f"
                        [Node "g" []]
                 , Node "h" []]
          , Node "i" []]


test1 = fmap ("dog" ++) t1

test2 = mapM_ putStrLn (preorder t1)

test3 = mapM_ putStrLn (preorder test1)