The sum of products style

To explore datatype-generic functions in the sum of products style, we'll return to the familiar List and Tree values:

  data List' a = Nil' | Cons' a (List' a)
      deriving (Show)

  data Tree a = Node a (Tree a) (Tree a)
          | Leaf a
            deriving (Show)

  aList = (Cons' 2 (Cons' 3 (Cons' 5 Nil')))
intTree 
 = Node 2 (Leaf 3) 
                 (Node 5 (Leaf 7) 
                               (Leaf 11))

As a reference point, we define the datatype-specific size functions:

  sizeT (Leaf _) = 1
  sizeT (Node _ lt rt) 
    = 1 + (sizeT lt) + (sizeT rt)

  sizeL Nil' = 0
  sizeL (Cons' _ xs)
    = 1 + (sizeL xs)

As is the case with recursive functions over recursive types, notice how the shape of functions follows the shape of the underlying recursive datatype.

Instead of these ad hoc polymorphic functions, let's write them in a datatype-generic way. First, we define a type representation. In this...