Solutions to Chapter 3 (p. 60)

#1. Given the List definition:

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

We can define toList thus:

toList (Cons a as) = a : toList as
toList Nil = []

Each line replaces the List constructor with the matching [a] constructor: Cost is replaced by :, whereas Nil is replaced by an empty list. Because the built-in list type [a] is defined using recursion, so is this conversion process.

#2.

data Tree a = Node a (Maybe (Tree a)) (Maybe (Tree a))
              deriving (Show)