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 types:

  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)

Instead of these ad hoc polymorphic functions, let's write them in a datatype-generic way. First, we define a type representation. In this section, we follow the generic programming style of Lightweight Implementation of Generics and Dynamics (LIGD) by Cheney and Hinze, 2002, as revised in Libraries for Generic Programming in Haskell by Jeuring et al., 2009...