There is a primal type that underlies recursive datatypes, known as Fix:

  data List' a = Nil'   | Cons' a (List' a)
  data Tree  a = Leaf a | Node  a (Tree a) (Tree a)

  data Fix s a = FixT {getFix :: s a (Fix s a)}

The parameter s represents the shape, while a refers to an instance of the type. The Fix datatype is named after the fixed point of a function, which is defined by:

  f (fix f) = fix f

To express Tree and List in terms of Fix, we need to rewrite them using implicit recursion:

  data List_ a r = Nil_    | Cons_ a r
    deriving (Show)
  data Tree_ a r = Leaf_ a | Node_ a r r
    deriving (Show)

Here, we replaced the explicit recursive reference with a more vague type parameter r. This allows us to express ListF and TreeF in terms of Fix:

  type ListF a = Fix List_ a
  type TreeF a = Fix Tree_ a

The List_ and Tree_ types don't explicitly recur, so Fix ties the recursive knot around the shape (refer to Datatype-Generic Programming by Gibbons). We can construct a List_ instance in a similar way:

aList1 = Cons_ 12 Nil_ 
­­-- aList :: List_ Integer (List_ a r) 
 
aList2 = Cons_ 12 (Cons_ 13 Nil_)  
­­-- aList2 :: List_ Integer (List_ Integer (List_ a r)) 

Although the type signatures show that this is quite different from regular lists, to construct the ListF lists, we need to wrap the FixT constructor around each nesting:

aListF :: ListF Integer -- Fix List_ Integer
aListF = FixT (Cons_ 12  
                      (FixT (Cons_ 13  
                                  (FixT Nil_))))

We deconstructed List and Tree into the generic recursion type Fix. This means we can write generic functions against the Fix type.

To find our way toward a generic map, let's write a map function for the recursive type ListF:

mapL f listF = case list_ of
   (Cons_ x r) 
        -> FixT $ Cons_ (f x) (mapL f r)
   Nil_  
        -> FixT Nil_
  where  list_ = getFix listF

showListF :: (Show a) => ListF a -> String
showListF (FixT (Cons_ x r)) 
  = (show x) ++ ", " ++ (showListF r)
showListF (FixT (Nil_)      
  = "Nil_"

main = putStrLn . showListF $ mapL (*2) aListF

This is clumsy because in both clauses of the case statement we have to unwrap the list (with getFix) and then wrap the result again (with FixT). The BiFunctor typeclass gives us what we need to clarify our mapL function:

The Bifunctor type-class is just a Functor that can have two functions applied to it instead of one (which is already defined in Data.Bifunctor):

class Bifunctor s where
  bimap :: (a -> c) -> (b -> d) -> (s a b -> s c d)

Let's make List_ and Tree_ types instances of the BiFunctor type-class:

instance Bifunctor List_ where
  bimap f g Nil_        = Nil_
  bimap f g (Cons_ x r) = Cons_ (f x) (g r)

instance Bifunctor Tree_ where
  bimap f g (Leaf_ x)       = Leaf_ (f x)
  bimap f g (Node_ x rl rr) = Node_ (f x) (g rl) (g rr)

Now, we can write a generic map:

gmap :: Bifunctor s => (a -> b) -> Fix s a -> Fix s b
gmap f = FixT . bimap f (gmap f) . getFix

main = putStrLn . showListF $ gmap (*2) aListF

We can also use the bimap function to implement a generic fold function :

gfold :: Bifunctor s => (s a b -> b) -> Fix s a -> b
gfold f = f . bimap id (gfold f) . getFix

Again, we unwrap the list with getFix, but this time, instead of rewrapping, we apply f. In other words, gfold replaces all occurrences of FixT with f:

-- FixT (Cons_ 12 (FixT (Cons_ 13 (FixT Nil_))))
-- f    (Cons_ 12 (f    (Cons_ 13 (f    Nil_))))

To fold together a sum, we create an adder:

addL (Cons_ x r) = x + r
addL Nil_        = 0
main = print $ gfold addL aListF

Where fold is a consumer of data structures, unfold is a producer that unfolds a structure from a single value. To unfold a regular list, we need a value and some functions:

unfoldL stopF nextF val
  = if stopF val -- stop if True
    then []
    else val : 
         (unfoldL stopF nextF (nextF val))

main = print $ unfoldL (< (-10)) (x -> x - 1) 10

We can use the bimap function to create a generic unfold:

gunfold :: Bifunctor s => (b -> s a b) -> b -> Fix s a
gunfold f = FixT . bimap id (gunfold f) . f

For example, we can use gunfold to generate a list of values from a single value:

toList 0 = Nil_
toList n = (Cons_ n (n-1))

main = putStrLn . showListF $ gunfold toList 10
--     10, 9, 8, 7, 6, 5, 4, 3, 2, 1, Nil_

Composing unfold with fold makes sense because by doing so, we are connecting a producer with a consumer:

main = print $ gfold addL (gunfold toList 100)

(Refer to Gibbons' Origami programming and Datatype-generic programming, where you will find this pattern under hylomorphisms.)

The unfold and fold functions are each other's mirror images:

  gunfold f = FixT . bimap id (gunfold f) . f
  gfold f   = f    . bimap id (gfold f)   . getFix

The hylo function is their composition:

hylo f g = g . bimap id (hylo f g) . f
main = print $ hylo toList addL 100

Jeremy Gibbons demonstrates that four Gang of Four design patterns are captured by the recursion operators of Origami Programming: