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.

#2.

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

6 comments:

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

    .. a newbie

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

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

    Not in scope: type constructor or class `Node'

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

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

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

    ReplyDelete
  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!

    ReplyDelete