RE: Strange error in show for datatype
Interesting. The difficulty (which GHCi has too) is this. Consider expr = Str "foo" msg = show expr Hugs wants to print msg. What are the types? expr :: forall a. LispList a msg :: forall a. Show a => String Urk! What "Show" dictionary should Hugs use when evaluating "msg"? You may say "it doesn't matter", but in general that's not the case. In the case of class Num, for example, we might have expr = 3+4 msg = show expr and then the type involved really does matter. In the case of Num there are defaulting rules, but not for arbitrary user types. What is particularly annoying here is that it's intuitively obvious that if we have an expression of type (forall a. LispList a) then it can't have any useful values of type 'a' in it. So we can't need to show any of them. Hmm. I wonder if the following is true. Given the ambiguous type forall a. Show a => T (where a does not appear in T) it's OK to pass the bottom dictionary. Furthermore, I claim that what makes it OK is that Show has no methods that have 'a' in the result that do not also have 'a' in an argument. The Bad Methods are like those in Num and Read: class Num a where fromInteger :: Integer -> a -- Bad guy ... class Read a where read :: String -> a -- Bad guy ... So (my claim) if none of the classes of the ambiguous type have a method that returns an a-value, we can definitely replace the dictionary with bottom. Indeed, if none of the classes have a method that returns an a-value without also consuming one (urk-- strictly, I think, sigh) then the same holds. In which case we could report ambiguity a bit less often. How useful this would be I don't know. Simon | For a change, a teacher asking for help on behalf of a student.... | | I have a student who wants to emulate S-expressions of Lisp | in Haskell. He came up with the following data type: | | data LispList t = Atom t | LispList [LispList t] | Str [Char] | | This works just fine. He then wanted to make it an instance | of Show, in order to print values of this type: | | instance Show t => Show (LispList t) where | show (Atom t) = show t | show (LispList t) = show t | show (Str t) = show t | | Now, this compiles and works for some values of the type, but | not for all! Here is what happens in hugs: | | hugsprompt> (Atom 1) ==> 1 | hugsprompt> (LispList [Atom 1, Str "HEJ"]) ==> [1,"HEJ"] (LispList | hugsprompt> [Atom 1, LispList [Str "HEJ"]]) ==> [1, ["HEJ"]] (Str | hugsprompt> "HEJ") ==> "Cannot find show function...." | (LispList [Str | hugsprompt> "HEJ"]) ==> "Cannot find show function...." | (LispList [Str | hugsprompt> "HEJ",Atom 1]) ==> "Cannot find show function...." | | So there is a problem when the value is of form Str string or | where such a value is first in the list l in a value of the | form LispList l. Oddly enough, such values may appear at | other positions without causing any problems. | | I don't think there is a bug in hugs. Similar problems appear | if the Show instance is derived, and ghc will also complain - | if the definition f = show (LispList [Str "HEJ"]) is | compiled, for instance, the compiler will complain about | ambiguous contexts. Ghc will say | | Enrico.hs:1: Ambiguous context `{Show taKi}' | `Show taKi' arising from use of `show' at | Enrico.hs:17 | | and hugs | | Reading file "Enrico.hs": | Type checking | ERROR "Enrico.hs" (line 17): Unresolved top-level overloading | *** Binding : f | *** Outstanding context : Show b | | So I wonder whether the infamous Monomorphism Restriction is | lurking somewhere here? But I cannot see exactly how right | now. Does anyone else have a clue? | | Björn | | _______________________________________________ | Haskell mailing list | Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell |
Simon Peyton-Jones wrote:
... msg :: forall a. Show a => String
Urk! What "Show" dictionary should Hugs use when evaluating "msg"?
You may say "it doesn't matter", but in general that's not the case. In the case of class Num, for example, we might have
expr = 3+4 msg = show expr
and then the type involved really does matter.
I wonder if the following is true. Given the ambiguous type
forall a. Show a => T (where a does not appear in T)
it's OK to pass the bottom dictionary. ...
Type systems with subtyping have what is needed to determine when the choice of dictinionary "doesn't matter". In type systems with subtyping, the most general type is the minimal type. This means that type variables that occur only positively (in covariant positions) can be minimized (and that negative variables can be maximized). If there is an empty type, Empty say, which is a subtype of all other types, then the type forall a . Show a => T is just as general as the type Show Empty => T since a occurs only positively in Show a => T, taking into account the occurences of a in the definition of the Show class. The requirement that a does not appear in T is overly restrictive. This simplification can be made as long as all occurences of a in T are positive. Assuming a language with subtyping that simplifes types in this way, expressions like show undefined show [] show Nothing show (Left False) would no longer be ambiguously overloaded. If the prelude provides instance Show Empty -- no methods need to be defined then types of the above expressions would all reduce to String, and they would all compute to the expected results (i.e., the result you would get by manually disambiguating the types, e.g., show ([]::[Int])). The same trick applies to the Eq class, so that, e.g., [] == [] would be unambiguous and compute to True. So, obviously, the next version of Haskell should have a type system with subtyping, don't you agree? :-) Thomas Hallgren PS In some previous version of Haskell (1.3?), the Prelude defined an empty type called Void, but it has since been removed. Apparently, people didn't see the potential of Void... PPS For those who are afraid of subtypes :-), I think you can use the information about variance of type variables used in subtype inference, to determine when the choice of dictinonary "doesn't matter", without introducing subtyping in the languange...
participants (2)
-
Simon Peyton-Jones -
Thomas Hallgren