Exercises

1. The prelude PreludeList of Haskell98 contains a number of functions that are defined by means of a foldr (a catamorphism). Find at least five other functions in the prelude that can be defined as a catamorphism on lists, and give their definitions as a catamorphism.
2. Catamorphisms can be defined in terms of function cata:

         
     cata :: Regular d => (FunctorOf d a b -> b) -> (d a -> b)    
     cata phi = phi . F (cata phi) . out
   

   Define the functions out and F (and probably a new type) in Haskell on the datatypes [a] and Tree a (see Thesis page 2), such that the following definitions define the catamorphisms on these datatypes.

     cataTree phi = phi . fTree (cataTree phi) . outTree
     cataList phi = phi . fList (cataList phi) . outList
   

3. Define function anaList :: (b -> Maybe (a,b)) -> (b -> [a]) so that anaList f is an anamorphism for lists.
4. Define function zip' (a variant of the prelude function zip):

   zip' :: ([a],[b]) -> [(a,b)]

   as an anamorphism.
5. Fusion:
   1. Write function length as a [a] catamorphism.
   2. Write function insertion_sort as a [a] catamorphism.
   3. Use fusion to prove that

        length . insertion_sort = length
      

6. Define minimum and reverse as catamorphisms on Tree a. Instantiate (mechanically, don't try to be clever!) the banana split theorem to obtain a Tree a catamorphism for the split of minimum and reverse in Haskell. The result can be further simplified - try to do it algebraically.
7. The datatype PairList a is defined by

      data PairList a = PLNil
                      | PLCons a (PairList (a,a))
   

   1. Define, in Haskell, a map on this datatype. (Hint: use so-called polymorphic recursion.)
   2. Can you instantiate the polytypic map on this datatype?
8. Define a polytypic function that calculates the maximum `depth' of a value of any datatype.

      depth :: d a -> Int
   

   For example,

      depth (Just 1) = 1
      depth [5, 2, 1] = 3
      depth (Bin (Leaf 6) (Bin (Bin (Leaf 3)(Leaf 6)) (Leaf 8))) = 3.
   

9. Consider the function flatten defined in PolyLib. Since this definition uses ++ in the g*h case, it is rather inefficient: it is quadratic in the size of its argument. The standard trick to obtain a linear-time program is to use an `accumulating parameter': replace flatten by a function flatten'

      flatten = flatten' []
   
      flatten' :: d a -> [a] -> [a]
   

   Define the polytypic function flatten'.
10. Define balance :: [a] -> Tree a as a Tree-anamorphism.
11. Define mapTree using cataTree.

Resources

Misc. definitions

(-*-)    :: (a -> c) -> (b -> d) -> (      (a,b) ->       (c,d))
(-+-)    :: (a -> c) -> (b -> d) -> (Either a b  -> Either c d )

f -*- g  =  \(x,y) -> (f x, g y)
f -+- g  =  either (Left . f) (Right . g)

split :: (a->b) -> (a->c) -> (a-> (b,   c  ))
split      f         g    =  \x-> (f x, g x)

Banana Split

split (cata f) (cata g) = cata (split (f . fmap2 id fst) (g . fmap2 id snd))

Examples

• Using ana and cata on Tree a (PolyP output).

Solutions