Real World Haskell Chapter 3 excercise: Binary Tree with 1 Value Constructor

Question

Chapter 3 defines the following recursive type for representing a binary tree:

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

The exercise requires me to implement the same type using the same 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, for example, our Java example. Instead of the Empty constructor, use the Maybe type to refer to node 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 a tree containing other empty trees, for example:

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

And I'm not sure why, "Nothing" is not a constructor of values ​​like "Maybe"?

Answer 1

This is not a Nothing value constructor that causes your error. You have two branches that you pass to the top-level tree that must be of type Maybe (AltTree a) , but both (AltNode 2 Nothing Nothing) and (AltNode 3 Nothing Nothing) are of type AltTree Int . You must use the Just value constructor to create Maybe values. how

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