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