Haskell - Use Just or no Just made difference, but I don't know why...

Question

Hello everyone, I've found such code in the book "Real World Haskell", p68

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

nodeAreSame (Node a _ _) (Node b _ _)
            | a == b = Just a
nodeAreSame _ _ = Nothing

My question is: What job did the Just data constructor do? When I delete it, I will get error message such like

(in ghci)
......
<Main *> nodeAreSame (Node 3 Empty Empty) (Node 3 Empty Empty))  

<interactive>:1:16:  
    No instance for (Num (Maybe a))
......

But when I try to compare the type difference between "Just" and "No Just" version:

nodeAreSameJust   :: (Eq t) => Tree t -> Tree t -> Maybe t

nodeAreSameNoJust :: (Eq a) => Tree (Maybe a) -> Tree (Maybe a) -> Maybe a

So what is the key point here? Does it means when I put a var with type a in the node, the function will not output a node with type a, so it get an error?

Answer 1

What else would you expect to return, simply a? That won't work, because a and Nothing aren't the same type. All definitions of a function have to return the same type. Nothing and Just a match because they're both of type Maybe a.

Answer 2

In the no Just version, it requires the item in the tree to be type Maybe a.

I'm not entirely sure the reason the error is for instance of Num (Maybe a). I think the error is more enlightening if you use a string instead of the 3.

*Main> nodeAreSameNoJust (Node "arst" Empty Empty) (Node "arst" Empty Empty)
<interactive>:1:24:

Couldn't match expected type `Maybe a'
       against inferred type `[Char]'
In the first argument of `Node', namely `"arst"'
In the first argument of `nodeAreSameNoJust', namely
    `(Node "arst" Empty Empty)'
In the expression:
    nodeAreSameNoJust
      (Node "arst" Empty Empty) (Node "arst" Empty Empty)

Here it's more clear that it's expecting something of type Maybe a. In both cases, the second case of the function is Nothing, so the result type is inferred to be Maybe a. By including the Just, the value you use in the tree are then put into a maybe type. Without this, it expects the resulting a to be the same type as Nothing, since each part of the function needs to be the same type.

Answer 3

In fact, the absence of Just does not make it ill-typed.

Here's the deal. The code

nodeAreSame (Node a _ _) (Node b _ _)
            | a == b = a
nodeAreSame _ _ = Nothing

is well-typed provided that a and b are of type Maybe t for some t, since that's the type of Nothing. Thus the type system makes this inference.

Now, when you have a numeric literal like 3, it is inferred to be of type Num s => s until you actually commit it to a particular data type (like Int or Double).

So when it puts these two facts together, it presumes the following:

Num (Maybe t) => 3 :: Maybe t.

As there is no instance for Num (Maybe t), it complains at that point, before getting a chance to complain that 3 :: Maybe t makes no sense.