10

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?

Improve this question
1

1 Answer 1

Reset to default
8

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))
Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

@rr Also, the solution is incomplete - you have no equivalent for Empty. You need to allow AltNode Nothing Nothing Nothing. That still isn't quite right, because now the type system can allow empty nodes that have children. Perhaps wrapping all the arguments into a Maybe tuple will be semantically better?
@Matajon, thanks for the explanation, that makes sense now. But does this not make the type different from the implementation they give in the book? Or perhaps I'm reading into this too much.
@Thomas M. DuBuisson That's a good point, I'm not entirely sure, I'll have to play around with it. Thanks.
@EnricoMariaDeAngelis Not sure what you mean by my "doubt about the impossibility of..." - I never said anything about an impossibility. SPOILER: The solution is to write the entire set of values in a maybe, such as data AN a = AN (Maybe (a,AN a,AN a)).
@EnricoMariaDeAngelis Ah yes I see. That is what I meant. If it isn't apparent to you, or surprising me with a contradiction, then that is worth a question.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.