Interaction and ambiguous type variables

[Ralf Hinze]

Dear all,

I am posting the following bug report every once in a while.
It describes a recurring and annoying problem (which I call
bug). It's annoying for beginners and students and it's
annoying for instructors, as well.

Here we go (using Hugs all along, but ghci is not that different).

------------------------------------------------------------------------------

<< Instructor:
implement `mirror' (aka reverse).

<< Student:

> mirror :: [a] -> [a]
> mirror [] = []
> mirror (a : as) = mirror as ++ [a]

But, I have a problem: the program does not work.

Main> mirror []
ERROR - Cannot find "show" function for:
*** Expression : mirror []
*** Of type    : [a]

<< Instructor:
it's because `mirror []' has the polymorphic type `[a]' and the
compiler cannot determine the `Show' instance for `a'. You can
find further explanations at
	http://www.cs.ukc.ac.uk/people/staff/sjt/craft2e/errors.html
[All this is jolly difficult to explain in the first week of
a Haskell course. It's annyoing because the result is, of course, the
empty list. Yes, I know that the empty list can be printed in
different ways depending on the type:
Main> mirror [] :: [Int]
[]
Main> mirror [] :: String
""
Alas, I don't think this justifies the trouble.]

<< Instructor:
implement `turn' (aka mirror or reverse) on trees.

<< Student:

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

> turn :: Tree a -> Tree a
> turn Empty = Empty
> turn (Node l a r) = Node (turn r) a (turn l)

But, I have a problem: the program does not work.
Main> turn Empty
ERROR - Cannot find "show" function for:
*** Expression : turn Empty
*** Of type    : Tree a

<< Instructor:
<see above>
[Now, the result is obvious and there is only one way to print it!
Yes, I know that we can complicate matters slightly so that the
result is again ambiguous in print.
Main> turn (Node Empty [] Empty)
ERROR - Cannot find "show" function for:
*** Expression : turn (Node Empty [] Empty)
*** Of type    : Tree [a]

Main> turn (Node Empty [] Empty) :: Tree [Int]
Node Empty [] Empty
Main> turn (Node Empty [] Empty) :: Tree String
Node Empty "" Empty

Again, it's only the empty list that may come out in different
shapes. But, things still can get worse.]

<< Instructor:

implement a test that checks whether a list is ordered.

<< Student:

> ordered :: (Ord a) => [a] -> Bool
> ordered [] = True
> ordered [a] = True
> ordered (a : b : as) | a <= b    = ordered (b : as)
>                      | otherwise = False

But, I have a problem: the program does not work.
Main> ordered []
ERROR - Unresolved overloading
*** Type       : Ord a => Bool
*** Expression : ordered []

<< Instructor:
<see above>
[Now, we have not even a problem of ambiguity. The expression is not
ambiguous.]

------------------------------------------------------------------------------

The general problem is that the expression submitted to Hugs or GHC has a
polymorphic type *or* that a subexpression has a polymorphic type (as
in the last example). A simple solution is to monomorphize the type
instantiating all type variables to, say, the empty type `Void'.
Additionally, we have to add instances for the standard classes 

instance Show Void
instance Eq Void

etc.

Why do we need instances for all the classes? If a subexpression has
a polymorphic type, then other classes may be affected.
Main> [] == []
ERROR - Unresolved overloading
*** Type       : Eq a => Bool
*** Expression : [] == []

------------------------------------------------------------------------------

Let me close by saying that I think it's important to address this
problem because it bites students again and again and again ...

Cheers, Ralf