Real World Haskell Chapter 3 excercise: Binary Tree with 1 value constructor

Question

Chapter 3 defines the following recursive type to represent a binary tree:

data Tree a = Node a (Tree a) (Tree a)
            | Empty
              deriving (Show)

The exercise requires I implement the same type using a single value constructor, using the "Maybe" type to refer to child nodes:

(From Chapter 3 Exercise 2 on page 60)

"Define a tree type that has only one constructor, like our Java example. Instead of the Empty constructor, use the Maybe type to refer to a node's children."

The solution I came up with is the following:

data AltTree a = AltNode a (Maybe (AltTree a)) (Maybe (AltTree a))
                 deriving (Show)

However, this does not allow for a tree containing other empty trees, such as:

AltNode 1 (AltNode 2 Nothing Nothing) (AltNode 3 Nothing Nothing)

And I'm not sure why, is "Nothing" not a value constructor for the "Maybe" type?

Answer 1

It's not the Nothing value constructor which causes your error. You two branches you pass to the top-level tree should have type Maybe (AltTree a), but both (AltNode 2 Nothing Nothing) and (AltNode 3 Nothing Nothing) have type AltTree Int. You have to use Just value constructor to create values of Maybe type from them. Like

AltNode 1 (Just (AltNode 2 Nothing Nothing)) (Just (AltNode 3 Nothing Nothing))