module RoseTree where


-- A tree whose nodes can have an arbitrary finite number of children is sometimes called
-- a "Rose Tree". Our particular variant stores a value of type 'a' at each node, at at each leaf.

data RoseTree a = Node a [RoseTree a]
                | Leaf a
  deriving (Show)

-- A rose tree is a functor, meaning it has a "map" function. This function
-- applies a given function f :: A -> B to every value in a rose tree, preserving
-- the tree structure.

instance Functor RoseTree where
  fmap f (Node v children) = (Node (f v) (map (fmap f) children))
  fmap f (Leaf v) = (Leaf (f v))

-- It also has a fold, which you can think of as replacing every occurrence
-- of the "Node" constructor with "nf" and every occurrence of the "Leaf"
-- constructor with "lf".
--
-- For example. foldRoseTree (\ v cs -> RoseTree v cs) (\ v -> Leaf v)
-- will give you back the original rose tree!

foldRoseTree :: (a -> [b] -> b) ->  (a -> b) -> (RoseTree a) -> b
foldRoseTree nf lf (Node v children) = nf v (map (foldRoseTree nf lf) children)
foldRoseTree nf lf (Leaf v) = lf v

-- exercise: Implement fmap for RoseTree in terms of foldRoseTree

-- some examples

-- First, if we want to say, add one to every value stored in a rose tree of
-- integers, we simply do

treePlusOne :: RoseTree Integer -> RoseTree Integer
treePlusOne = fmap (+1)

-- We could also map all the 0 values to True and all the nonzero values to False

treeIntToBool :: RoseTree Integer -> RoseTree Bool
treeIntToBool = fmap (\x -> if x == 0 then True else False)

-- we can also use fold to do some more complicated things, for example
-- we could sum all the values in an integer rose tree by doing

treeSum :: RoseTree Integer -> Integer
treeSum = foldRoseTree (\ v vs -> v + (sum vs)) id

-- finally, an example RoseTree Integer for you to play with. (try drawing it if you
-- are having trouble visualizing the structure!)

exampleTree :: RoseTree Integer
exampleTree = (Node 3 [(Node 4 [(Leaf 7),(Node 5 [(Leaf 6)])]),(Leaf 1),(Node 2 [(Leaf 3)])])