--list
data List a = Empty | Node a (List a)

map':: (a->b)->List a->List b
map' f Empty = Empty
map' f (Node a list) = Node (f a) (map' f list)

foldr':: (a->b->b)->b->List a->b
foldr' f acc Empty = acc
foldr' f acc (Node a list) = f a (foldr' f acc list)

foldl':: (b->a->b)->b->List a->b
foldl' f acc Empty = acc
foldl' f acc (Node a list) = foldl' f (f acc a) list

zipWith'::(a->b->c) -> List a -> List b -> List c
zipWith' _ Empty _ = Empty
zipWith' _ _ Empty = Empty
zipWith' f (Node first firstList) (Node second secondList) = Node (f first second) (zipWith' f firstList secondList)

infixr 5 .++
(.++):: List a -> List a -> List a
Empty .++ list = list
(Node a list) .++ other = Node a (list .++ other)

fromNormalList:: [a]->List a
fromNormalList [] = Empty
fromNormalList (x:xs) = Node x (fromNormalList xs)

toNormalList:: List a -> [a]
toNormalList Empty = []
toNormalList (Node a list) = a : toNormalList (list)

instance Functor List where
    fmap = map'

instance Applicative List where
    pure a = Node a Empty
    fm <*> xm = fromNormalList [f x | f <- toNormalList fm, x <- toNormalList xm]

--tree
data Tree a = Tree a [Tree a]

generateTree:: a->Int->Int->Tree a
generateTree node 0 _ = Tree node []
generateTree node depth branches = Tree node (replicate branches (generateTree node (depth-1) branches))

instance Functor Tree where
    fmap f (Tree node []) = Tree (f node) []