Thursday, April 23, 2009

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.


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


  1. to #2:
    Nice, but the empty tree is not possible.

    .. a newbie

  2. Indeed! Then how about:

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

    The left and right children always exist, but each of them is a "Maybe" since the tree itself is a Maybe.

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

    Not in scope: type constructor or class `Node'

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

  5. But this will allow a leaf with branches (?!?).

    Nothing -- value is Nothing i.e. non-existant
    Nothing -- left
    (Just (Node (Just 3) Nothing Nothing)) -- right should not exist

    IMHO a node should always have a value.

  6. The exercise asks for the equivalent of the Java example. If you assume 'value' can never be null then Dr. Elkenstein's answer does the trick. If value can be null, then Vivek's answer is equivalent (you just basically tag a Maybe on every member). If you find that inconsistent like rabbitisle says, then I believe your only choice is the book's solution!