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 ...

Get Haskell Design Patterns now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.