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')))
    = 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 O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.