wrap x = [x]

data List a =
       Nil
     | Cons a (List a)

--map_L :: (a -> b) -> List a -> List b
map_L f Nil        = Nil
map_L f (Cons x xs)= Cons (f x) (map_L f xs)

data Tree a =
       Leaf a
     | Bin (Tree a) (Tree a)
--map_T :: (a -> b) -> Tree a -> Tree b
map_T f (Leaf x)  = Leaf (f x)
map_T f (Bin l r) = Bin (map_T f l) (map_T f r)

--cata_L :: b -> (a -> b -> b) -> List a -> b
cata_L e op Nil        = e
cata_L e op (Cons x xs) = op x (cata_L e op xs)

sum_L   = cata_L 0 (+)
all_L p = cata_L True (\x b -> (p x) && b)

--cata_T :: (a -> b) -> (b -> b -> b) -> Tree a -> b
cata_T f op (Leaf x)  = f x
cata_T f op (Bin l r) = op (ca l) (ca r)
           where ca = cata_T f op

map_T' :: (a -> b) -> Tree a -> Tree b
map_T' f   = cata_T (Leaf . f) Bin
  -- This definition is equivalent to the one above.
flatten_T :: Tree a -> [a]
flatten_T = cata_T wrap (++)
             where wrap x = [x]
  -- The structure is flattened to a list.
unzip_T :: Tree (a,b) -> (Tree a,Tree b)
unzip_T   = cata_T (app (Leaf,Leaf)) (app . app (Bin,Bin))
            where app (f,g) (a,b) =(f a,g b)
  -- Takes a tree of pairs and returns a pair of trees.
size_T :: Tree a -> Int
size_T    = cata_T (const 1) (\l r -> 1+l+r)
  -- Counts the number of constructors.
depth_T :: Tree a -> Int
depth_T   = cata_T (const 0) (\l r -> 1+(max l r))
  -- Calculates the maximal level of the constructors.
leftmost_T :: Tree a -> a
leftmost_T= cata_T id const
  -- returns the leftmost element of the tree.
mirror_T :: Tree a -> Tree a
mirror_T  = cata_T Leaf (flip Bin)
  -- Mirrors the tree in a line through its root.


test = Bin ( Bin ( Leaf (1,'P')) 
                 ( Leaf (2,'a')) )
           ( Bin ( Bin ( Leaf (3,'t')) 
                       ( Leaf (4,'r')))
                 ( Bin ( Leaf (5,'i')) 
                       ( Leaf (6,'k'))))

double t = Bin t t 
testn 0 = test
testn n = double (testn (n-1))