[Haskell-cafe] Re: Type classes
Forget it. It's more clear reading further. Sorry for the noise. On Sat, Dec 27, 2008 at 1:02 AM, Oscar Picasso oscarpica...@gmail.comwrote: From Real World Haskell: data JValue = JString String | JNumber Double | JBool Bool | JNull | JObject [(String, JValue)] | JArray [JValue] deriving (Eq, Ord, Show) type JSONError = String class JSON a where toJValue :: a - JValue fromJValue :: JValue - Either JSONError a instance JSON JValue where toJValue = id -- Really ? fromJValue = Right Now, instead of applying a constructor like JNumber to a value to wrap it, we apply the toJValue function. If we change a value's type, the compiler will choose a suitable implementation of toJValue to use with it. Actually it does not work. And I don't see how it could with this toJValue implementation. Is it possible to make it work by providing another implementation? Oscar ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Type classes in GADTs
On Wed, Oct 29, 2008 at 10:20 PM, C Rodrigues [EMAIL PROTECTED] wrote: I discovered that closed type classes can be implicitly defined using GADTs The GADT value itself acts like a class dictionary. However, GHC (6.83) doesn't know anything about these type classes, and it won't infer any class memberships. In the example below, an instance of Eq is not recognized. So is this within the domain of GHC's type inference, not something it shoud infer, or a bug? {-# OPTIONS_GHC -XTypeFamilies -XGADTs -XEmptyDataDecls #-} module CaseAnalysisOnGADTs where -- Commutative and associative operators. data CAOp a where Sum:: CAOp Int Disj :: CAOp Bool Concat :: CAOp String I guess when you write something like this the type checker doesn't look at the closed set of types that 'a' can take on. I don't know why that would be a problem in your example, but if we did this: data CAOp a where Sum :: CAOp Int Disj :: CAOP Bool Concat :: CAOp String Weird :: Show a = CAOp a Now we have a problem, because the set of types for is { Int, Bool, String, forall a. Show a = a}. It's not a closed set anymore. And I think, but I'm just making this up, that the above set of type must be hard to reason about. I think it would essentially be: data Show a = CAOp a where ... And GHC won't allow that, presumably for a good reason. Neat example, and I hope someone sheds more light on this. By the way, since you mention ghc6.8.3, does that mean some other version of GHC permits noEvidenceOfEq to type check? I tried 6.6.1 but that didn't accept it either. Jason ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Type classes in GADTs
Jason Dagit wrote: On Wed, Oct 29, 2008 at 10:20 PM, C Rodrigues [EMAIL PROTECTED] wrote: I discovered that closed type classes can be implicitly defined using GADTs The GADT value itself acts like a class dictionary. However, GHC (6.83) doesn't know anything about these type classes, and it won't infer any class memberships. In the example below, an instance of Eq is not recognized. So is this within the domain of GHC's type inference, not something it shoud infer, or a bug? {-# OPTIONS_GHC -XTypeFamilies -XGADTs -XEmptyDataDecls #-} module CaseAnalysisOnGADTs where -- Commutative and associative operators. data CAOp a where Sum:: CAOp Int Disj :: CAOp Bool Concat :: CAOp String I guess when you write something like this the type checker doesn't look at the closed set of types that 'a' can take on. I don't know why that would be a problem in your example, but if we did this: data CAOp a where Sum :: CAOp Int Disj :: CAOP Bool Concat :: CAOp String Weird :: Show a = CAOp a Now we have a problem, because the set of types for is { Int, Bool, String, forall a. Show a = a}. It's not a closed set anymore. And I think, but I'm just making this up, that the above set of type must be hard to reason about. I think it would essentially be: data Show a = CAOp a where ... I agree with Jason here. Actually we can think of quite a lot of examples where the type checker _can_ know something what we see as obvious. But that something is a special case of a more general situation which is far less obvious and knowing it may require serious program analysis. Then, regarding handling some special cases, I think it's a matter of keeping type checker predictable and clean. In this particular case, handling this situation would require type checker to look at the _values_ of the given datatype, which as I understand Haskell type checker doesn't. If we later add members to CAOp the valid program may become invalid, though the signature of CAOp hasn't changed. That doesn't look good. Not all members of CAOp may be exported from a module, that would have to be taken into account as well, probably. In your example, why not just do traditionalEvidenceOfEq :: Eq a = D a - Bool -- Daniil Elovkov ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: Type classes in GADTs
Thanks for the explanation. I see how this wouldn't behave nicely with automatic class constraint inference. I didn't test the example on any other GHC versions. I will probably end up passing in the Eq dictionary from outside like Daniil suggested. I would prefer to do the following, but GHC doesn't accept the type signature. evidenceOfEq :: CAOp a - (Eq a = b) - b Neither does it accept data EqConstraint a b = EqConstraint (Eq a = b). Foiled again. _ Want to read Hotmail messages in Outlook? The Wordsmiths show you how. http://windowslive.com/connect/post/wedowindowslive.spaces.live.com-Blog-cns!20EE04FBC541789!167.entry?ocid=TXT_TAGLM_WL_hotmail_092008___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Type classes in GADTs
2008/10/30 C Rodrigues [EMAIL PROTECTED]: evidenceOfEq :: CAOp a - (Eq a = b) - b isn't that the same as: evidenceOfEq :: Eq a = CAOp a - b - b Neither does it accept data EqConstraint a b = EqConstraint (Eq a = b). Foiled again. same here: data Eq a = EqConstraint a b = EqConstraint b. although this must be a typo, since it doesn't make any sense to me. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
[Haskell-cafe] Re: Type classes question
Ryan Ingram ryani.spam at gmail.com writes: [...] Here's another possible solution: newtype AsFunctor s a = AF { fstream :: (s a) } instance (Stream f) = Functor (AsFunctor f) where fmap f (AF s) = AF (fmapStreamDefault f s) Now to use fmap you wrap in AF and unwrap with fstream. None of the existing solutions are really satisfactory, unfortunately. Bulat Ziganshin bulat.ziganshin at gmail.com writes: http://haskell.org/haskellwiki/OOP_vs_type_classes may be useful Many thanks to you both for the clarification and pointers. cheers, Roly ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: type classes
class RingTy a b where order :: a - Integer units :: a - [b] class VectorSpaceTy a b | a - b where dimension :: a - Integer basis :: (Field c) = a - [b c] where `b' is a vector space over the field `c'. It looks like you are using the first (of two) type arguments to the RingTy and VectorSpaceTy type classes as abstract types; in other words, operations on rings and vector spaces don't really care what the type a is in RingTy a b and VectorSpaceTy a b. Is that true? Assuming so, if I may strip away the (extremely sweet) syntactic sugar afforded by type classes for a moment, what you seem to be doing is to pass dictionaries of types data RingTy a b = RingTy { order :: a - Integer, units :: a - [b] } data VectorSpaceTy a b = VectorSpaceTy { dimension :: a - Integer, basis :: forall c. (Field c) = a - [b c] } to operations on rings and vector spaces. Because the type a is abstract, you may as well pass dictionaries of types data RingTy b = RingTy { order :: Integer, units :: [b] } data VectorSpaceTy b = VectorSpaceTy { dimension :: Integer, basis :: forall c. (Field c) = [b c] } to these operations. The information that you want computed just once per ring or per vector space can be defined as lexically scoped variables where you create these dictionaries in the first place. To add back the syntactic sugar (i.e., to make the dictionary arguments implicit) and to make the type system check that elements of different vector spaces are not confused, you may find Dylan Thurston's technique useful: http://www.cs.rutgers.edu/~ccshan/prepose/prepose.pdf -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 2008-07-04 Independence from America! http://caab.org.uk/ 2008-07-05 International Co-operative Day http://ica.coop/ http://www.guardian.co.uk/politics/2008/jul/02/labour.tradeunions ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: type classes
Slightly off-topic - but I'm curious to know why you want objects representing the structures as well as the elements - what will they be used for? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: type classes
A number of operations -- like order above -- are conceptually connected not to the elements but to the structures themselves. Here is the outline of a more complicated example. I also have a vector space class class VectorSpaceTy a b | a - b where dimension :: a - Integer basis :: (Field c) = a - [b c] where `b' is a vector space over the field `c'. Suppose I have a haskell function `f :: a c - b c' representing a linear transformation between (elements) of two vector spaces. I can write transformationMatrix :: VectorSpaceTy ta a - VectorSpaceTy tb b - (a c - b c) - Matrix c to compute the matrix of the linear transformation. Another alternative is something like ModuleBasis from the numeric prelude: class (Module.C a v) = C a v where {- | basis of the module with respect to the scalar type, the result must be independent of argument, 'Prelude.undefined' should suffice. -} basis :: a - [v] To compute the basis (for type reasons?) basis needs an (ignored) element of the vector space, but this seems ugly to me. In my case, the vector space is the space of modular forms. Computing a basis requires a tremendous amount of work. I only want to do it once. The ...Ty object gives me a place to stash the result. How would you do this? Cotton On Thu, Jul 3, 2008 at 7:01 AM, DavidA [EMAIL PROTECTED] wrote: Slightly off-topic - but I'm curious to know why you want objects representing the structures as well as the elements - what will they be used for? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Type classes: Missing language feature?
DavidA wrote: newtype Lex = Lex Monomial deriving (Eq) newtype Glex = Glex Monomial deriving (Eq) Now, what I'd like to do is have Lex and Glex, and any further monomial orderings I define later, automatically derive Show and Num instances from Monomial (because it seems like boilerplate to have to define Show and Num instances by hand). Good news: it's already implemented and called newtype deriving :) http://www.haskell.org/ghc/docs/latest/html/users_guide/type-extensions.html#newtype-deriving In short, you just write newtype Lex = Lex Monomial deriving (Eq, Show, Num) I guess that the Show instance will add the constructor Lex , though. Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Type classes vs C++ overloading Re: [Haskell-cafe] Messing around with types [newbie]
I sent this message yesterday to Bulat but it was intended for the haskel cafe, so I'm resending it here today. Thank to everyone who answered me privately. Today I'll keep on experimenting and read the reference you gave me. Cristiano -- Forwarded message -- From: Cristiano Paris [EMAIL PROTECTED] Date: Jun 21, 2007 6:20 PM Subject: Re: Type classes vs C++ overloading Re: [Haskell-cafe] Messing around with types [newbie] To: Bulat Ziganshin [EMAIL PROTECTED] On 6/21/07, Bulat Ziganshin [EMAIL PROTECTED] wrote: Hello Cristiano, Thursday, June 21, 2007, 4:46:27 PM, you wrote: class FooOp a b where foo :: a - b - IO () instance FooOp Int Double where foo x y = putStrLn $ (show x) ++ Double ++ (show y) this is rather typical question :) I knew it was... :D unlike C++ which resolves any overloading at COMPILE TIME, selecting among CURRENTLY available overloaded definitions and complaining only when when this overloading is ambiguous, type classes are the RUN-TIME overloading mechanism your definition of partialFoo compiled into code which may be used with any instance of foo, not only defined in this module. so, it cannot rely on that first argument of foo is always Int because you may define other instance of FooOp in other module. 10 is really constant function of type: 10 :: (Num t) = t i.e. this function should receive dictionary of class Num in order to return value of type t (this dictionary contains fromInteger::Integer-t method which used to convert Integer representation of 10 into type actually required at this place) this means that partialFoo should have a method to deduce type of 10 in order to pass it into foo call. Let's consider its type: partialFoo :: (FooOp t y) = y - IO () when partialFoo is called with *any* argument, there is no way to deduce type of t from type of y which means that GHC has no way to determine which type 10 in your example should have. for example, if you will define instance FooOp Int32 Double where anywhere, then call partialFoo (5.0::Double) will become ambiguous shortly speaking, overloading resolved based on global class properties, not on the few instances present in current module. OTOH, you build POLYMORPHIC functions this way while C++ just selects best-suited variant of overloaded function and hard-code its call further reading: http://homepages.inf.ed.ac.uk/wadler/papers/class/class.ps.gz http://haskell.org/haskellwiki/OOP_vs_type_classes chapter 7 of GHC user's guide, functional dependencies M... your point is hard to understand for me. In his message, I can understand Bryan Burgers' point better (thanks Bryan) and I think it's somewhat right even if I don't fully understand the type machinery occuring during ghc compilation (yet). Quoting Bryan: *From this you can see that 10 is not necessarily an Int, and 5.0 is *not necessarily a Double. So the typechecker does not know, given just 10 and 5.0, which instance of 'foo' to use. But when you explicitly told the typechecker that 10 is an Int and 5.0 is a Double, then the type checker was able to choose which instance of 'foo' it should use. So, let's see if I've understood how ghc works: 1 - It sees 5.0, which belongs to the Fractional class, and so for 10 belonging to the Num class. 2 - It only does have a (FooOp x y) instance of foo where x = Int and y = Double but it can't tell whether 5.0 and 10.0 would fit in the Int and Double types (there's some some of uncertainty here). 3 - Thus, ghci complains. So far so good. Now consider the following snippet: module Main where foo :: Double - Double foo = (+2.0) bar = foo 5.0 I specified intentionally the type signature of foo. Using the same argument as above, ghci should get stuck in evaluating foo 5.0 as it may not be a Double, but only a Fractional. Surprisingly (at least to me) it works! So, it seems as if the type of 5.0 was induced by the type system to be Double as foo accepts only Double's. If I understand well, there's some sort of asymmetry when typechecking a function application (the case of foo 5.0), where the type signature of a function is dominant, and where typechecking an overloaded function application (the original case) since there type inference can't take place as someone could add a new overloading later as Bulat says. So, I tried to fix my code and I came up with this (partial) solution: module Main where class FooOp a b where foo :: a - b - IO () instance (Num t) = FooOp t Double where foo x y = putStrLn $ (show x) ++ Double ++ (show y) partialFoo :: Double - IO () partialFoo = foo 10 bar = partialFoo 5.0 As you can see, I specified that partialFoo does accept Double so the type of 5.0 if induced to be Double by that type signature and the ambiguity disappear (along with relaxing the type of a to be simply a member of the Num class so 10 can fit in anyway). Problems arise if I add another instance of FooOp where b is Int (i.e. FooOp Int Int): module
Re: Type classes vs C++ overloading Re: [Haskell-cafe] Messing around with types [newbie]
On Fri, Jun 22, 2007 at 10:57:58AM +0200, Cristiano Paris wrote: Quoting Bryan: *From this you can see that 10 is not necessarily an Int, and 5.0 is *not necessarily a Double. So the typechecker does not know, given just 10 and 5.0, which instance of 'foo' to use. But when you explicitly told the typechecker that 10 is an Int and 5.0 is a Double, then the type checker was able to choose which instance of 'foo' it should use. I would stress typechecker does not know, given just 10 and 5.0, which instance of 'foo' to use. The statement 10 is not necessarily an Int may be misleading. I would rather say 10 can be not only Int, but also any other type in the Num type class. So, let's see if I've understood how ghc works: 1 - It sees 5.0, which belongs to the Fractional class, and so for 10 belonging to the Num class. 2 - It only does have a (FooOp x y) instance of foo where x = Int and y = Double but it can't tell whether 5.0 and 10.0 would fit in the Int and Double types (there's some some of uncertainty here). The problem is not that it can't tell whether 5.0 and 10 would fit Int and Double (actually, they do fit), it's that it can't tell if they won't fit another instance of FooOp. 3 - Thus, ghci complains. So far so good. Now consider the following snippet: module Main where foo :: Double - Double foo = (+2.0) bar = foo 5.0 I specified intentionally the type signature of foo. Using the same argument as above, ghci should get stuck in evaluating foo 5.0 as it may not be a Double, but only a Fractional. Surprisingly (at least to me) it works! See above. So, it seems as if the type of 5.0 was induced by the type system to be Double as foo accepts only Double's. I think that's correct. If I understand well, there's some sort of asymmetry when typechecking a function application (the case of foo 5.0), where the type signature of a function is dominant, and where typechecking an overloaded function application (the original case) since there type inference can't take place as someone could add a new overloading later as Bulat says. There is no asymmetry. The key word here is *ambiguity*. In the (Double - Double) example there is no ambiguity - foo is not overloaded, in other words it's a single function, so it suffices to check if the parameters have the right types. In your earlier example, both 5.0 and foo are overloaded. If you had more instances for FooOp, the ambiguity could be resolved in many ways, possibly giving different behaviour. Haskell doesn't try to be smart and waits for you to decide. And it pretends it doesn't see that there is only one instance, because taking advantage of this situation could give surprising results later. but it didn't work. Here's ghci's complaint: example.hs:7:0: Duplicate instance declarations: instance (Num t1, Fractional t2) = FooOp t1 t2 -- Defined at example.hs:7:0 instance (Num t1, Num t2) = FooOp t1 t2 -- Defined at example.hs:10:0 Failed, modules loaded: none. Instances are duplicate if they have the same (or overlapping) instance heads. An instance head is the thing after =. What's before = doesn't count. It seems that Num and Fractional are somewhat related. Any hint? It's not important here, but indeed they are: class (Num a) = Fractional a where Best regards Tomek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Type classes vs C++ overloading Re: [Haskell-cafe] Messing around with types [newbie]
On 6/22/07, Tomasz Zielonka [EMAIL PROTECTED] wrote: ... The problem is not that it can't tell whether 5.0 and 10 would fit Int and Double (actually, they do fit), it's that it can't tell if they won't fit another instance of FooOp. You expressed the concept in more correct terms but I intended the same... I'm starting to understand now. Instances are duplicate if they have the same (or overlapping) instance heads. An instance head is the thing after =. What's before = doesn't count. So, the context is irrelevant to distinguishing instances? It seems that Num and Fractional are somewhat related. Any hint? It's not important here, but indeed they are: class (Num a) = Fractional a where I see. Thank you Tomasz. Cristiano ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Type classes vs C++ overloading Re: [Haskell-cafe] Messing around with types [newbie]
Bulat Ziganshin wrote: Hello Cristiano, Thursday, June 21, 2007, 4:46:27 PM, you wrote: class FooOp a b where foo :: a - b - IO () instance FooOp Int Double where foo x y = putStrLn $ (show x) ++ Double ++ (show y) this is rather typical question :) unlike C++ which resolves any overloading at COMPILE TIME, selecting among CURRENTLY available overloaded definitions and complaining only when when this overloading is ambiguous, type classes are the RUN-TIME overloading mechanism As I understood it, it was at COMPILE TIME (i.e. no type witness) whenever explicitly type-annotated, implicitly when not exported from a module, or when inlined at the call site, at least in GHC. Or did I get this wrong? Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Type classes and type equality
- If we permit overlapping instances extension, then a few lines of code decide equality for all existing and future types: class TypeEq x y b | x y - b instance TypeEq x x HTrue instance TypeCast HFalse b = TypeEq x y b This is exactly what I was after, but it doesn't seem to work in Hugs - even with overlapping instances and unsafe overlapping instances turned on. Hugs is indeed quite problematic; back in 2004 we essentially gave up on Hugs for anything moderately advanced, especially after Ralf found an example which typechecks only if constraints are specified in a particular order. If we permute the constraints (I think, it was in the instance declaration), Hugs complaints. Clearly the order of constraints should not matter. It has been my experience that the code requiring undecidable instances on GHC might not work on Hugs, failing with sometimes bizarre error messages. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Type classes and type equality
Hi Oleg, I'm looking for a type class which checks whether two types are the same or not. For the full discussion of various solutions, please see Section 9 and Appendix D of the HList paper: http://homepages.cwi.nl/~ralf/HList/paper.pdf Thanks for pointing that out. As far as I can see, this requires a new instance declaration for every type? In this sense, it would require as many Typeable declarations, but have the downside that it isn't build into any compiler. I was really hoping for something that requires less work on behalf of the user. Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Type classes and type equality
Thanks for pointing that out. As far as I can see, this requires a new instance declaration for every type? I guess it depends on how many extensions one may wish to enable. At the very least we need multi-parameter type classes with functional dependencies (because that's what TypeEq is in any case). - If we permit no other extension, we need N^2 instances to compare N classes for equality (basically, for each type we should say how it compares to the others). This is not practical except in very limited circumstances. - If we permit undecidable instances, one may assign numerals to types. This gives us total order and hence comparison on types. In this approach, we only need N instances to cover N types. This is still better than Typeable because the equality is decided and can be acted upon at compile time. - If we permit overlapping instances extension, then a few lines of code decide equality for all existing and future types: class TypeEq x y b | x y - b instance TypeEq x x HTrue instance TypeCast HFalse b = TypeEq x y b Please see http://www.haskell.org/pipermail/haskell-cafe/2006-November/019705.html for some less conventional application, with the complete code. I was really hoping for something that requires less work on behalf of the user. The latter approach may be suitable then. It requires no work on behalf of the user at all: the type comparison is universal. http://darcs.haskell.org/HList There is also an issue of ground vs unground types. All the approaches above can decide equality for sufficiently grounded types. That is, two types can be decided equal only if they are ground. The disequality may be decided for partially ground types. If the types are non-ground, the TypeEq constraint flows up, to be resolved when the types are sufficiently instantiated. It is possible to decide equality of non-ground types and even naked type variables. That is a separate discussion. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Type classes and type equality
Hi I guess it depends on how many extensions one may wish to enable. At the very least we need multi-parameter type classes with functional dependencies (because that's what TypeEq is in any case). - If we permit no other extension, we need N^2 instances to compare N classes for equality (basically, for each type we should say how it compares to the others). This is not practical except in very limited circumstances. - If we permit undecidable instances, one may assign numerals to types. This gives us total order and hence comparison on types. In this approach, we only need N instances to cover N types. This is still better than Typeable because the equality is decided and can be acted upon at compile time. In my particular case whether I act at compile time or run time is unimportant, but obviously this is an important advantage in general. Unfortunately a cost of one instance per type is still higher than I'd like to pay :-) - If we permit overlapping instances extension, then a few lines of code decide equality for all existing and future types: class TypeEq x y b | x y - b instance TypeEq x x HTrue instance TypeCast HFalse b = TypeEq x y b This is exactly what I was after, but it doesn't seem to work in Hugs - even with overlapping instances and unsafe overlapping instances turned on. *** This instance: TypeEq a b c *** Conflicts with : TypeEq a a HTrue *** For class: TypeEq a b c *** Under dependency : a b - c Is there any way to modify this to allow it to work under Hugs as well? Thanks very much for your help, Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Type classes and type equality
On Wed, Apr 18, 2007 at 01:47:04AM +0100, Neil Mitchell wrote: - If we permit undecidable instances, one may assign numerals to types. This gives us total order and hence comparison on types. In this approach, we only need N instances to cover N types. This is still better than Typeable because the equality is decided and can be acted upon at compile time. In my particular case whether I act at compile time or run time is unimportant, but obviously this is an important advantage in general. Unfortunately a cost of one instance per type is still higher than I'd like to pay :-) Now, it requires one line of code: {-# OPTIONS_DERIVE --derive=TTypeable #-} Stefan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Type classes
Geest, == Geest, G van den [EMAIL PROTECTED] writes: Geest, I suppose you want to define compareEntries like this: compareEntries (Entry x) (Entry y) = compareEntries x y Geest, An option is to just implement it the following way Geest, (Haskell98!): class DatabaseEntry e where entryLabel :: e - String formatEntry :: e - String compareEntries :: e - e - Ordering data Entry a = Entry a No. I don't want that. The database parsing function returns Map.Map String Entry but entries can of different types (and these type vary over styles). -- WBR, Max Vasin. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Type classes
Then you should produce 'some canonical representation for database entries suited for comparison', like Stefan mentioned. For example: data Entry = forall a. (DatabaseEntry a) = Entry a instance DatabaseEntry Entry where entryLabel (Entry e) = entryLabel e formatEntry (Entry e) = formatEntry e compareEntries (Entry x) (Entry y) = compare (entryLabel x) (entryLabel y) Gerrit Max Vasin wrote: Geest, == Geest, G van den [EMAIL PROTECTED] writes: Geest, I suppose you want to define compareEntries like this: compareEntries (Entry x) (Entry y) = compareEntries x y Geest, An option is to just implement it the following way Geest, (Haskell98!): class DatabaseEntry e where entryLabel :: e - String formatEntry :: e - String compareEntries :: e - e - Ordering data Entry a = Entry a No. I don't want that. The database parsing function returns Map.Map String Entry but entries can of different types (and these type vary over styles). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Type classes
Stefan == Stefan Holdermans [EMAIL PROTECTED] writes: Stefan Max, class DatabaseEntry e where entryLabel :: e - String formatEntry :: e - String compareEntries :: e - e - Ordering Then I define data Entry = forall a. (DatabaseEntry a) = Entry a instance DatabaseEntry Entry where entryLabel (Entry e) = entryLabel e formatEntry (Entry e) = formatEntry e How can I define compareEntries for this instance? Stefan In general: you can't. The field of the Entry constructor has Stefan a existentially quantified typed. Given two arbitrary values Stefan of type Entry, this type may be instantiated with a different Stefan type for each value, so you cannot easily compare the fields. Yes, this require something like multimethods in CLOS. Stefan If you extend the DatabaseEntry class such that it supplies a Stefan method that allows to produce some canonical representation Stefan for database entries suited for comparison, then you could Stefan take that road. Stefan Are you sure that your Entry type needs to be existentially Stefan quantified? I want a map of entries (mapping lables to entries). Generally each style can define its own data types for database objects. Converting entries from data BibEntry = { beLabel :: String , beKind :: String , beProperties :: Map.Map String String } is some sort of static type checking of the database. -- WBR, Max Vasin. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Type classes and definite types
Hi Bryn Keller, The solution for your problem is very simple. You just have to fetch all values as strings. In this way the library will do all required conversions for you. printRow stmt = do id - getFieldValue stmt ID code - getFieldValue stmt Code name - getFieldValue stmt Name putStrLn (unwords [id, code, name]) Cheers, Krasimir On 5/6/05, Bryn Keller [EMAIL PROTECTED] wrote: Max Vasin wrote: Bryn Keller [EMAIL PROTECTED] writes: Hi Max, Hello Bryn, Thanks for pointing this out. It's odd that I don't see that anywhere in the docs at the HToolkit site: http://htoolkit.sourceforge.net/doc/hsql/Database.HSQL.html but GHC certainly believes it exists. However, this doesn't actually solve the problem. Substituting toSqlValue for show in printRow' gives the same compile error: Main.hs:22:18: Ambiguous type variable `a' in the constraint: `SqlBind a' arising from use of `getFieldValue' at Main.hs:22:18-30 Probable fix: add a type signature that fixes these type variable(s) So, like with (show (read s)), we still can't use the function until we've established a definite type for the value, not just a type class. Yeah... Some more RTFSing shows that we have the getFieldValueType :: Statement - String - (SqlType, Bool) which allows us to write printRow stmt = do (id :: Int) - getFieldValue stmt ID let (codeType, _) = getFieldValueType stmt Code codestr - case codeType of SqlChar _ - do (c :: String) - getFieldValue stmt Code return (toSqlValue c) SqlInteger - do (i :: Int) - getFieldValue stmt Code return (toSqlValue i) -- etc for all SqlType data constructors putStrLn (unwords [show id, codestr]) At least it compiles. But it's ugly :-( Ah, good point! Ugly it may be, but at least it works. Thanks for the idea! Bryn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Type classes confusion
Ah. I just need to drop the context from the data type declaration. Sorry, Andrew andrew cooke said: Hi, I'm trying to use type classes and suspect I've got confused somewhere down the line, because I've got to an error message that I don't understand and can't remove. I have a class that works like a hash table, mapping from String to some type. I have two instances, one that is case insensitive for keys. I want to hide these instances from the rest of the code, which should only use the class. This class is called Dictionary. In addition, for Dictionaries that map Strings to Strings, I have some functions which do substitutions on Strings using their own contents. Possibly the first source of problems is that I can't find a way to express these two classes together without multiple parameter type classes (one parameter for the case/no case and one for the type returned): class Dictionary d a where add' :: d a - (String, a) - d a ... instance Dictionary DictNoCase a where add' d (k, v) = ... -- Dict is the underlying tree implementation and Maybe stores the -- value for the null (empty string) key. data DictNoCase a = DictNoCase (Dict a) (Maybe a) class (Dictionary d String) = SubDictionary d where substitute :: d String - String - String ... instance SubDictionary DictNoCase where substitute d s = ... All the above compiles and seems correct (is it?). I also provide an empty instance of the two instance types. For DictNoCase, this is empty = DictCase Empty Nothing where Empty is the empty type constructor for Dict Now (almost there) elsewhere I want to define a data type that contains two of these Dictionaries. One stores String values. The other stores functions that take this same type and return a result and a copy of the type: data Context s f = (Dictionary s String, Dictionary f (CustomFn s f)) = Ctx {state :: s String, funcs :: f (CustomFn s f)} type CustomFn s f = Context s f - Arg - IO (Context s f, Result s f) data Result s f = Attr Name String | Repeat (CustomFn s f) ... newContext = Ctx empty emptyNC (where empty is the case-sensitive empty dictionary) Now THAT doesn't compile: Template.lhs:60: All of the type variables in the constraint `Dictionary s String' are already in scope (at least one must be universally quantified here) When checking the existential context of constructor `Ctx' In the data type declaration for `Context' Template.lhs:60: All of the type variables in the constraint `Dictionary f (CustomFn s f)' are already in scope (at least one must be universally quantified here) When checking the existential context of constructor `Ctx' In the data type declaration for `Context' where line 60 is data Context And I can't see what I've done wrong. Any help gratefully received. Cheers, Andrew -- personal web site: http://www.acooke.org/andrew personal mail list: http://www.acooke.org/andrew/compute.html ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell -- personal web site: http://www.acooke.org/andrew personal mail list: http://www.acooke.org/andrew/compute.html ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: type classes, superclass of different kind
Robert Will wrote: Note that in an OO programming language with generic classes ... (We shouldn't make our functional designs more different from the OO ones, than they need to be.) why should *we* care :-) more often than not, OO design is resticted and misleading. you see how most OO languages jump through funny hoops (in this case, generics) because they just lack proper higher-order types. good luck with your library. but make sure you study existing (FP) designs, e. g. Chris Okasaki's Edison: http://www.eecs.usma.edu/Personnel/okasaki/pubs.html#hw00 -- -- Johannes Waldmann, Tel/Fax: (0341) 3076 6479 / 6480 -- -- http://www.imn.htwk-leipzig.de/~waldmann/ - ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: type classes, superclass of different kind
Robert Will wrote: Now I would like to have Collection to be a superclass of Map yielding the following typing reduce :: (Map map a b) = ((a, b) - c) - c - map a b - c Note that in an OO programming language with generic classes (which is in general much less expressive than real polymorphism), I can write class MAP[A, B] inherit COLLECTION[TUPLE[A, B]] which has exactly the desired effect (and that's what I do in the imperative version of my little library). There seems to be no direct way to achieve the same thing with Haskell type classes (or any extension I'm aware of). Here is a quesion for the most creative of thinkers: which is the design (in proper Haskell or a wide-spread extension) possibly include much intermediate type classes and other stuff, that comes nearest to my desire? I don't know if I qualify as the most creative of thinkers, but I have a small library of ADSs that you may want to look at, it's at http://www.dtek.chalmers.se/~d00nibro/algfk/ I recall having much the same problem as you did, my solution was to make maps (or Assoc as I call them) depend on tuple types, i.e. (somewhat simplified): class (Collection c (k,v), Eq k) = Assoc c k v where lookup :: k - c (k,v) - v [...many more member functions here...] This means that the type constructors for maps and collections have the same kind (* - *), which makes it possible for me to say that an Assoc is actually also a Collection. A lot more info to be found off the link. I believe this question to be important and profound. (We shouldn't make our functional designs more different from the OO ones, than they need to be.) If I err, someone will tell me :- No need to recreate all the stupid things the OO world has come up with, better to do it correctly right away... ;) /Niklas Broberg, d00nibro[at]dtek.chalmers.se _ The new MSN 8: advanced junk mail protection and 2 months FREE* http://join.msn.com/?page=features/junkmail ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: type classes, superclass of different kind
--- Robert Will [EMAIL PROTECTED] wrote: -- Here -- is a quesion for the -- most creative of thinkers: which is the design (in -- proper Haskell or a -- wide-spread extension) possibly include much -- intermediate type classes and -- other stuff, that comes nearest to my desire? Hello, I've often wondered the same thing. I've found that one can simulate several OO paradigms. Note that these aren't particularly elegant or simple. Using Data Constructors: data Shape = Rectangle {topLeft :: (Int, Int), bottomRight :: (Int,Int) } | Circle {center :: (Int,Int), radius :: Int } This allows you have a list of shapes shapeList :: [Shape] shapeList = [ Rectangle (-3,3) (0,0), Circle (0,0) 3 ] When you want member functions, you need to specialize the function for all the constructors. height :: Shape - Int height (Rectangle (a,b) (c,d)) = b - d height (Circle _ radius) = 2 * radius Disadvantages: 1) When a new Shape is needed, one needs to edit the original Shape source file. 2) If a member function is not implemented for a shape subclass, it will lead to a run-time error (instead of compile-time). Advantages: 1) Simple Syntax 2) Allows lists of Shapes 3) Haskell98 Example: GHC's exception types http://www.haskell.org/ghc/docs/latest/html/base/Control.Exception.html Using Classes Classes can be used to force a type have specific functions to act upon it. From our previous example: class Shape a where height :: a - Int data Rectangle = Rectangle {topLeft :: (Int, Int), bottomRight :: (Int,Int) } data Circle = Circle {center :: (Int,Int), radius :: Int } instance Shape Circle where height (Circle _ radius) = 2 * radius instance Shape Rectangle where height (Rectangle (a,b) (c,d)) = b - d In this case, something is a shape if it specifically has the member functions associated with Shapes (height in this case). Advantages 1) Simple Syntax 2) Haskell98 3) Allows a user to easily add Shapes without modifying the original source. 4) If a member function is not implemented for a shape subclass, it will lead to a compile-time error. Disadvantages: 1) Lists of Shapes not allowed Example: Haskell 98's Num class. http://www.haskell.org/ghc/ Classes with Instance holder. There have been a few proposals of ways to get around the List of Shapes problem with classes. The Haskell98 ways looks like this data ShapeInstance = ShapeInstance { ci_height :: Int } toShapeInstance :: (Shape a) = a - ShapeInstance toShapeInstance a = ShapeInstance { ci_height = (height a) } instance Shape ShapeInstance where height (ShapeInstance ci_height) = ci_height So when we want a list of shapes, we can do shapeList = [ toShapeInstance (Circle (3,3) 3), toShapeInstance (Rectangle (-3,3) (0,0) ) ] Of course this also has it's disadvantages. Everytime a new memeber function is added, it must be noted in the ShapeInstance declaration, the toShapeInstance function, and the instance Shape ShapeInstance declaration. Using a haskell extention, we can get a little better. Existentially quantified data constructors gives us this: data ShapeInstance = forall a. Shape a = ShapeInstance a instance Shape ShapeInstance where height (ShapeInstance a) = height a shapeList = [ ShapeInstance (Circle (3,3) 3), ShapeInstance (Rectangle (-3,3) (0,0) ) ] The benefits of this method are shorter code, and no need to update the ShapeInstance declaration every time a new member function is added. Records extention A different kind of inheritance can be implemented with enhanced haskell records. See http://research.microsoft.com/~simonpj/Haskell/records.html and http://citeseer.nj.nec.com/gaster96polymorphic.html for in depth explinations. I'm not sure if these have been impemented or not, but it would work as follows. The inheritance provided by the above extentions is more of a data inheritance than a functional inheritance. Lets say all shapes must have a color parameter: type Shape = {color :: (Int,Int,Int)} type Circle = Shape + { center :: (Int,Int), radius :: (Int) } type Rectangle = Shape + { topLeft :: (Int,Int), bottomRight :: (Int, Int) } So now we can reference this color for any shape by calling .color. getColor :: (a : Shape ) - a - (Int,Int,Int) getColor a = a.color I'm not sure how the records extention could be used with Classes with instance holders to provide an even more plentiful OO environment. So I'll conclude this email with the observation that Haskell supports some OO constructs although not with the most elegance. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: type classes, superclass of different kind
On Thu, 11 Dec 2003, Robert Will wrote: Hello, As you will have noticed, I'm designing a little library of Abstract Data Structuresm here is a small excerpt to get an idea: class Collection coll a where ... (+) :: coll a - coll a - coll a reduce :: (a - b) - b - coll a - b ... class Map map a b where ... (+) :: map a b - map a b - map a b at :: map a b - a - b ... Note that the classes don't only share similar types, they also have similar algebraic laws: both + and + are associative, and neither is commutative. Now I would like to have Collection to be a superclass of Map yielding the following typing reduce :: (Map map a b) = ((a, b) - c) - c - map a b - c Functional dependencies will do this. class Collection coll a | coll - a where ... (+) :: coll - coll - coll reduce :: (a - b - b) - b - coll - b ... class (Collection map (a,b)) = Map map a b | map - a b where ... (+) :: map - map - map at :: map - a - b Now you make instances like instance Collection [a] a where (+) = (++) reduce = foldr instance (Eq a) = Map [(a,b)] a b where new + old = nubBy (\(x,_) (y,_) - x == y) (new ++ old) at map x = fromJust (lookup x map) Note that in an OO programming language with generic classes (which is in general much less expressive than real polymorphism), I can write class MAP[A, B] inherit COLLECTION[TUPLE[A, B]] which has exactly the desired effect (and that's what I do in the imperative version of my little library). This isn't exactly the same thing. In the OO code the interface collections must provide consists of a set of methods. A particular type, like COLLECTION[INTEGER] is the primitive unit that can implement or fail to implement that interface. In the Haskell code you require a collection to be a type constructor that will give you a type with appropriate methods no matter what you apply it to (ruling out special cases like extra compace sequences of booleans and so on). A map is not something that takes a single argument and makes a collection, so nothing can implement both of your map and collection interfaces. The solution is simple, drop the spurrious requirement that collections be type constructors (or that all of our concrete collection types were created by applying some type constructor to the element type). The classes with functional dependencies say just that, our collection type provides certain methods (involving the element types). Collections were one of the examples in Mark Jones' paper on functional dependencies (Type Classes with Functional Dependencies, linked from the GHC Extension:Functional Dependencies section of the GHC user's guide). There seems to be no direct way to achieve the same thing with Haskell type classes (or any extension I'm aware of). Here is a quesion for the most creative of thinkers: which is the design (in proper Haskell or a wide-spread extension) possibly include much intermediate type classes and other stuff, that comes nearest to my desire? I believe this question to be important and profound. (We shouldn't make our functional designs more different from the OO ones, than they need to be.) If I err, someone will tell me :- What problems do objects solve? They let you give a common interface to types with the same functionality, so you can make functions slightly polymorphic in any argument type with the operations your code needs. They organize your state. Then let you reuse code when you make a new slightly different type. Am I missing anything here? I think type classes are a much better solution than inheritance for keeping track of which types have which functionality. (at least the way interface by inheritance works in most typed and popular object oriented languages.) Inheritance only really works for notions that only involve the type doing the inheriting, or are at least heavly centered around that type. I don't think Functor can be represented as an interface, or at least not a very natural one. Most langauges I know of (see Nice for an exception) also require you to declare the interface a class supports when you declare it, which is really painful when you want your code to work with types that were around before you were, like defining a class to represent marshallable values for interface/serialization code. Are there any advantages to inheritance for managing interfaces? Maybe it takes a few minutes less to explain the first time around. It's probably easier to implement. Beyond that, I see nothing. Any creative thinkers want to try this? (An answer here would motivate an extension to the type class system, of course). Brandon Robert ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Type classes and code generation
I had a discussion with someone over the type class mechanism and would like to clarify something. When I compile this trivial program: module Main where main = putStrLn (show (1 + 2)) with ghc -Wall, the compiler says: Main.lhs:3: Warning: Defaulting the following constraint(s) to type `Integer' `Num a' arising from the literal `2' at Main.lhs:3 This implies to me that the compiler is generating the code for (+) for the particular instance, rather than using a run-time dispatch mechanism to select the correct (+) function. Is this correct, or am I way off? Hi, I hope I've understod your question. What this message is telling you is that the compiler is applying Haskell 98's defaulting mechanism. The numeric literals 1 and 2 in the code are overloaded, that is they have type: Num a = a When the program is run the calls to '+' and 'show' must be resolved to particular instances. However the overloading of their arguments prevents that. The overloading is thus ambiguous. Haskell 98 has a rule that (very roughly) says when overloading is ambiguous and it involves standard numeric classes, apply some defaults to resolve the ambiguity. In this case the default rule is to resolve the outstanding constraint 'Num a' with Integer (making the type of 1 and 2 Integer). After defaulting the instances of + and show can be resolved. You can change the behaviour of defaulting, and even turn it off, try: module Main where default () ... Compiling again with -Wall gives: Ambiguous type variable(s) `a' in the constraint `Num a' arising from the literal `2' at Foo.hs:6 In the second argument of `(+)', namely `2' In the first argument of `show', namely `(1 + 2)' You can also get the same effect as defaulting by putting explicit type annotations in your program: main = putStrLn (show ((1 + 2) :: Integer)) The Haskell Report doesn't say a whole lot about _how_ to implement the type class overloading, though from what I understand, most implementations use a similar algorithm (dictionary passing). You can read all about typical implementations in the literature. Google for Type Class, Implementation, and maybe even Haskell. Does the compiler *always* know what the actual instances being used are? A smart compiler can specialise the calls to overloaded functions in circumstances when the type(s) of its arguments are also known. This is a good thing because it tends to reduce the cost of overloading at runtime. More aggresive forms of specialisation are also possible and discussed in the literature. I think if you look up the papers on implementing type classes your questions should be answered. Mail me if you need some references. Cheers, Bernie. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Type classes and code generation
Alistair Bayley writes: Warning: Defaulting the following constraint(s) to type `Integer' `Num a' arising from the literal `2' at Main.lhs:3 This implies to me that the compiler is generating the code for (+) for the particular instance, rather than using a run-time dispatch mechanism to select the correct (+) function. Is this correct, or am I way off? Does the compiler *always* know what the actual instances being used are? Yes, roughly. In Haskell, the compiler always figures out the types of everything at compile time. This means it can often figure out which bit of code to use at compile time as well - but because of polymorphism, not always. Consider this bit of code: double :: Num a = a - a double x = x + x The function double will work on any type in the class Num, so the compiler can't know which + function to use. But it *doesn't* solve this by run-time dispatch, like in C++. Instead, it compiles double like this: double' :: NumDict a - a - a double' d x = let f = plus d in x `f` x where NumDict is a record a bit like this: data NumDict a = NumDict { plus :: a - a - a, minus :: a - a - a, fromInteger :: Integer - a ... } NumDict is called a dictionary, and any time double' is called, the caller must supply the right dictionary. If you write double 2.0 then the compiler sees that you've written a Double, and so supplies the NumDict Double dictionary: double' doubleNum 2.0 where doubleNum :: NumDict Double contains the methods for adding Doubles, subtracting them, and converting from Integers to them. Whenever it can, a good optimising compiler (like GHC) will try to remove these extra dictionary applications, and use the code for the right method directly. This is called specialisation. Getting back to your original question, there's a little subtlety in Haskell to do with literals. Whenever you type an integer literal like 2, what the compiler actually sees is fromInteger 2. fromInteger has type Num a = Integer - a, so this means that when you type an integer literal it is automatically converted to whatever numeric type is appropriate for the context. In the context you give, there's still not enough information - it could be Int, or Integer, or Double, or several other things. Another little subtlety called defaulting (see the Haskell 98 Report, in section 4.3.4) arranges that in this situation, the compiler will assume you mean Integer if that works, and failing that, it will try Double before giving up. That's what the warning message you give is telling you. Is there some way of preventing the type mechanism from generating code for the instance type, as opposed to the class? I don't understand this question - does the explanation above help? If I am correct, does it work the same way across module boundaries? (I would think so.) Yes, it does work automatically across instance boundaries. If a module exports a class but no instances for that class, then a user of that class would have to install their own instances. Instance exporting is not easy to control in Haskell; if you export a type, then all its instances are exported along with it automatically. OTOH, if the class plus one or more instances were exported, then a user could use the supplied instance types, and the compiler would still generate code to use the specific instances. From the explanation above, you should see that the compiler generates polymorphic code for any function with a type class in its type (e.g., Num a = ...), and it's the *caller* that supplies the code for the specific instances (the dictionary). But if the type is known at compile time, then the compiler will fill in the dictionary itself, and may even specialise it away. The intention is that there is only one, global instance space - you can't tightly control the export or not of specific instances, they are pretty much always exported and all visible. This isn't quite true in practice, but it's the idea. Hope this helps. If you don't mind, I'm going to put this conversation up on the Wiki, at http://www.haskell.org/hawiki/TypeClass --KW 8-) ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: Type classes and code generation
Is there some way of preventing the type mechanism from generating code for the instance type, as opposed to the class? I don't understand this question - does the explanation above help? I could have been clearer with my questions. What I was wondering was: is there some situation where the compiler can't statically determine the type to be used? The function double will work on any type in the class Num, so the compiler can't know which + function to use. When it's applied, the compiler will know the types of the arguments, won't it?. Which means that you would generate a version of double for each (applied) instance of Num. I don't doubt that there's a good reason this is not done: code bloat? or are there simply some expressions that can't be statically resolved? I suppose I was thinking: is the language design sufficiently clever that it's *always* possible for the compiler to infer the type instance in use, or are there some situations where it's not possible to infer the instance, so some kind of function dispatch mechanism is necessary? Yes, roughly. In Haskell, the compiler always figures out the types of everything at compile time. This means it can often figure out which bit of code to use at compile time as well - but because of polymorphism, not always. Consider this bit of code: double :: Num a = a - a double x = x + x The function double will work on any type in the class Num, so the compiler can't know which + function to use. But it *doesn't* solve this by run-time dispatch, like in C++. Instead, it compiles double like this: double' :: NumDict a - a - a double' d x = let f = plus d in x `f` x where NumDict is a record a bit like this: data NumDict a = NumDict { plus :: a - a - a, minus :: a - a - a, fromInteger :: Integer - a ... } NumDict is called a dictionary, and any time double' is called, the caller must supply the right dictionary. If you write double 2.0 then the compiler sees that you've written a Double, and so supplies the NumDict Double dictionary: double' doubleNum 2.0 where doubleNum :: NumDict Double contains the methods for adding Doubles, subtracting them, and converting from Integers to them. This looks like a dispatching mechanism to me. However, I think I see that this can still be done at compile-time. When double is applied to 2.0, the compiler generates the double' doubleNum 2.0 code, which is still statically resolvable. The advantage seems to be that you don't generate a double function for each Num instance. Does this also mean that a dictionary class is created for every class, and a dictionary created for every instance? Getting back to your original question, there's a little subtlety in Haskell to do with literals. Whenever you type an integer literal like 2, what the compiler actually sees is fromInteger 2. Another little subtlety called defaulting (see the Haskell 98 Report, in section 4.3.4) arranges that in this I knew about the fromInteger and similar treatment of literals, but the defaulting system is news to me. I've skimmed over the Haskell report, but details like this never sink in until you encounter them in practice... Instance exporting is not easy to control in Haskell; if you export a type, then all its instances are exported along with it automatically. Thanks. I wasn't sure how the export mechanism worked with regard to classes and instances; I just took a (wrong) guess that you could control export of classes and types separately. * The information in this email and in any attachments is confidential and intended solely for the attention and use of the named addressee(s). This information may be subject to legal professional or other privilege or may otherwise be protected by work product immunity or other legal rules. It must not be disclosed to any person without our authority. If you are not the intended recipient, or a person responsible for delivering it to the intended recipient, you are not authorised to and must not disclose, copy, distribute, or retain this message or any part of it. * ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Type classes and code generation
Bayley, Alistair wrote: When it's applied, the compiler will know the types of the arguments, won't it?. Which means that you would generate a version of double for each (applied) instance of Num. I don't doubt that there's a good reason this is not done: code bloat? or are there simply some expressions that can't be statically resolved? I suppose I was thinking: is the language design sufficiently clever that it's *always* possible for the compiler to infer the type instance in use, or are there some situations where it's not possible to infer the instance, so some kind of function dispatch mechanism is necessary? This almost is an FAQ. Short answer: in general it is impossible to determine statically which instances/dictionaries are needed during evaluation. Their number may even be infinite. The main reason is that Haskell allows polymorphic recursion. Consider the following (dumb) example: f :: Eq a = [a] - Bool f [] = True f (x:xs) = x == x f (map (\x - [x]) xs) The number of instances used by f depends on the length of the argument list! Determining that statically is of course undecidable. If the list is infinite, f will use infinitely many instances (potentially, depending on lazy evaluation). Another (non-Haskell-98) feature that prevents static resolution of type class dispatch are existential types, which actually provide the equivalent to real OO-style dynamic dispatch. Of course, for most practical programs, the optimization you have in mind would be possible. I doubt compilers generally do it globally, though, because it requires whole program analysis, i.e. does not interfer well with separate compilation (beside other reasons). | Andreas -- Andreas Rossberg, [EMAIL PROTECTED] Computer games don't affect kids; I mean if Pac Man affected us as kids, we would all be running around in darkened rooms, munching magic pills, and listening to repetitive electronic music. - Kristian Wilson, Nintendo Inc. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Type classes and code generation
Does this also mean that a dictionary class is created for every class, and a dictionary created for every instance? Yes, exactly. Every class is translated to a data type declaration, and every instance is translated to an element of that data type - a dictionary. (Note that you can't actually write those declarations in Haskell 98 in general, because they can have polymorphic fields; but this is a simple extension to the language). Take a look at one of the references Bernard put on the bottom of the Wiki page I just created for further information. http://www.haskell.org/hawiki/TypeClass --KW 8-) ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Type classes and code generation
(Moved to the Cafe) Yes, exactly. Every class is translated to a data type declaration, and every instance is translated to an element of that data type - a dictionary. (Note that you can't actually write those declarations in Haskell 98 in general, because they can have polymorphic fields; but this is a simple extension to the language). Keith, could you elaborate on this parenthetical? Under what circumstances can you not create the dictionary datatype for a class in Haskell 98 (where the class itself is H98 :P)? - Hal ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Type classes and code generation
You need to change the first line to this: data C a = C { pair :: forall b. b - (b,a) } and then it works fine (with -fglasgow-exts). But you've now stepped outside the bounds of Haskell 98. (oops, replying to myself... sure sign of madness! :) ) I hasten to add that this is *not* the same as existential quantification; note carefully the location of the forall wrt the constructor. --KW 8-) -- Keith Wansbrough [EMAIL PROTECTED] http://www.cl.cam.ac.uk/users/kw217/ University of Cambridge Computer Laboratory. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Type classes problem: Could not deduce ...
Hi Dirk, [EMAIL PROTECTED] writes: Hello, trying to compile the following program class ClassA a where foo :: a - Int class ClassA a = ClassB b a where toA :: b - a test :: (ClassB b a) = b - Int test x = let y = toA x in let z = foo y in z I get a compilation error: TestTypeClasses.hs:12: Could not deduce (ClassB b a1) from the context (ClassB b a) Probable fix: Add (ClassB b a1) to the type signature(s) for `test' arising from use of `toA' at TestTypeClasses.hs:12 In a pattern binding: toA x Can anybody explain the problem to me or suggest workarounds? Adding (ClassB b a1) to the context does not solve the problem, it just generates an error of the same sort. Consider the type of the following application of toA: *Dirk :t toA (42::Int) forall a. (ClassB Int a) = a The type inference can't deduce much about the result type of the application because type classes only specify relations over types. In your case, ClassB is a binary relation over types. Hence, you could easily imagine having two instances for ClassB instance ClassB Int Bool instance ClassB Int Char putting the Int type into relation with more than a single other type. Judging from your member function toA, I guess you'd really like to say, that every type b of ClassB *uniquely determines* the second type a. This can be expressed by a type class with functional dependency[1]: class ClassA a = ClassB b a | b - a where toA :: b - a Cheers, Matthias [1] Mark P Jones, Type Classes with Functional Dependencies, ESOP 2000 -- Matthias Neubauer | Universität Freiburg, Institut für Informatik | tel +49 761 203 8060 Georges-Köhler-Allee 79, 79110 Freiburg i. Br., Germany | fax +49 761 203 8052 ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: type classes vs. multiple data constructors
G'day. On Mon, Feb 17, 2003 at 01:44:07AM -0500, Mike T. Machenry wrote: I was wondering if it's better to define them as type classes with the operations defined in the class. What do haskellian's do? I can't speak for other Haskellians, but on the whole, it depends. Here's the common situation: You have a family of N abstractions. (In your case, N=2.) The abstractions are similar in some ways and different in some ways. The most appropriate design depends largely on what those similarities and differences are. From your definitions, it seems clear that there is some common structure. That suggests that a vanilla type class solution may not be appropriate, because type classes do not directly support common structure, only related operations. Your solution wasn't bad: data PlayerState = FugitiveState { tickets :: Array Ticket Int, fHistory :: [Ticket] } | DetectiveState { tickets :: Array Ticket Int, dHistory :: [Stop] } If the operations on the tickets field are different, or the algorithms which operate on PlayerState are different for the FugitiveState case and the DetectiveState case, this may be a good design, because by not sharing structure, you're explicitly denying any similarity (i.e. just because look the similar, that doesn't mean they are similar). If they are similar, then this may not be an appropriate design. Ideally, you want to use language features and/or idioms which expose the similarities (where they exist) and the differences (where they exist). Here's one design where the structural similarity is explicit: data PlayerState = PlayerState { tickets :: Array Ticket Int, role:: RoleSpecificState } data RoleSpecificState = FugitiveState { fHistory :: [Ticket] } | DetectiveState { dHistory :: [Stop] } Depending on how similar the operations on the RoleSpecificState are (say, if they are related by a common type signature, but have little code in common), or if you want a design which is extensible to other kinds of player (possibly at dynamic-link time) you may prefer to use type classes to implement the role-specific states instead: -- Warning: untested code follows class RoleSpecificState a where {- ... -} data FugitiveState = FugitiveState { fHistory :: [Ticket] } instance RoleSpecificState FugitiveState where {- ... -} data DetectiveState = DetectiveState { fHistory :: [Ticket] } instance RoleSpecificState DetectiveState where {- ... -} data PlayerState = forall role. (RoleSpecificState role) = PlayerState { tickets :: Array Ticket Int, role:: role } (If you know anything about design patterns, you may recognise this as being similar to the Strategy pattern. This is no accident.) It's hard to say what is the most appropriate design without looking at the algorithms and operations which act on the PlayerState type and analysing their similarities and differences. Oh and if I say Instance Foo Baz where ... and only define a few of the operations in Foo... bdoes Baz take on some default methods? If you've declared default methods, yes. Cheers, Andrew Bromage ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: type classes and generality
On 09-Jul-2001, Norman Ramsey [EMAIL PROTECTED] wrote: I'm trying to model probability and leave the representation of probability unspecified other than it must be class Real. But I'm having trouble with random numbers; how can I show that if a type has class Real, it also has class Random.Random? Is there a way to accomplish this goal other than by changing the library? I'm not sure if I fully understand your goal. But one thing you can do is to define a wrapper type newtype WrapReal r = WrapReal r and make the wrapper an instance of Random.Random if the underlying type is an instance of Real instance Real r = Random.Random (WrapReal r) where ... Then you can use the wrapper type whenever you want to get a random number. -- Fergus Henderson [EMAIL PROTECTED] | I have always known that the pursuit The University of Melbourne | of excellence is a lethal habit WWW: http://www.cs.mu.oz.au/~fjh | -- the last words of T. S. Garp. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: type classes and generality
On 09-Jul-2001, Norman Ramsey [EMAIL PROTECTED] wrote: I'm trying to model probability and leave the representation of probability unspecified other than it must be class Real. But I'm having trouble with random numbers; how can I show that if a type has class Real, it also has class Random.Random? Is there a way to accomplish this goal other than by changing the library? I'm not sure if I fully understand your goal. But one thing you can do is to define a wrapper type newtype WrapReal r = WrapReal r and make the wrapper an instance of Random.Random if the underlying type is an instance of Real instance Real r = Random.Random (WrapReal r) where ... Then you can use the wrapper type whenever you want to get a random number. The problem is that without intensional type analysis, I wouldn't know how to fill in the instance methods in the `...' N ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: type classes and generality
On 09-Jul-2001, Norman Ramsey [EMAIL PROTECTED] wrote: On 09-Jul-2001, Norman Ramsey [EMAIL PROTECTED] wrote: I'm trying to model probability and leave the representation of probability unspecified other than it must be class Real. But I'm having trouble with random numbers; how can I show that if a type has class Real, it also has class Random.Random? Is there a way to accomplish this goal other than by changing the library? I'm not sure if I fully understand your goal. But one thing you can do is to define a wrapper type newtype WrapReal r = WrapReal r and make the wrapper an instance of Random.Random if the underlying type is an instance of Real instance Real r = Random.Random (WrapReal r) where ... Then you can use the wrapper type whenever you want to get a random number. The problem is that without intensional type analysis, I wouldn't know how to fill in the instance methods in the `...' How about like so? import Random newtype WrapReal r = WrapReal r wrap r = WrapReal r unwrap (WrapReal r) = r instance Real r = Random (WrapReal r) where random = randomR (wrap 0, wrap 1) randomR (min, max) gen0 = (wrap (fromInteger r), gen) where (r, gen) = randomR (imin, imax) gen0 imin = ceiling (toRational (unwrap min)) imax = floor (toRational (unwrap max)) Ah, now I think I understand your problem. You want to `random' to generate random numbers that span all the possible values of the type within the range [0, 1], or at least a substantial subset, but the Real class doesn't let you generate any numbers other than integers. The above approach will give you random numbers from `random', but they will only ever be 0 or 1, so maybe they are not as random as you needed! ;-) The proof that you can only generate integers values of the real type (by which I mean values of the real type for which toRational returns an integer) is that the only methods of class Real which return values of the type are fromInteger, and the operators (+, *, -, negate, abs, and signum), which are all integer-preserving -- when given integers they will always return other integers. So by induction you can't generate any non-integers. I'd advise you to add an extra Random t class constraint to those parts of your application that rely on generating random numbers. If you find yourself using `Real t, Random t' frequently, you can use a derived class for that: class (Random t, Real t) = RandomReal a where -- no methods -- Fergus Henderson [EMAIL PROTECTED] | I have always known that the pursuit The University of Melbourne | of excellence is a lethal habit WWW: http://www.cs.mu.oz.au/~fjh | -- the last words of T. S. Garp. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: type classes and generality
Hi All, Fergus Henderson wrote: Ah, now I think I understand your problem. You want to `random' to generate random numbers that span all the possible values of the type within the range [0, 1], or at least a substantial subset, but the Real class doesn't let you generate any numbers other than integers. The above approach will give you random numbers from `random', but they will only ever be 0 or 1, so maybe they are not as random as you needed! ;-) Each pseudorandom generator generates a countable sequence of values, which is isomorphic to a sequence of integers. In good old (Turbo)C we got something between 0 and MAXINT and then divided by (double)MAXINT. Can't _this_ be done in Haskell? Alexander ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: type classes and generality
On 09-Jul-2001, Alexander V. Voinov [EMAIL PROTECTED] wrote: Hi All, Fergus Henderson wrote: Ah, now I think I understand your problem. You want to `random' to generate random numbers that span all the possible values of the type within the range [0, 1], or at least a substantial subset, but the Real class doesn't let you generate any numbers other than integers. The above approach will give you random numbers from `random', but they will only ever be 0 or 1, so maybe they are not as random as you needed! ;-) Each pseudorandom generator generates a countable sequence of values, which is isomorphic to a sequence of integers. In good old (Turbo)C we got something between 0 and MAXINT and then divided by (double)MAXINT. Can't _this_ be done in Haskell? Sure, it can be done, but not on a value whose type is constrained only by the Real class, because the Real class doesn't have any division operator! Haskell's / operator is a member of the Floating class, and Floating is not a base class of Real. It is a base class of the RealFrac class, so you could use that approach for RealFrac... but the original poster was asking for the solution to a more difficult problem. -- Fergus Henderson [EMAIL PROTECTED] | I have always known that the pursuit The University of Melbourne | of excellence is a lethal habit WWW: http://www.cs.mu.oz.au/~fjh | -- the last words of T. S. Garp. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: type classes and generality
Alexander V. Voinov wrote: Hi All, Fergus Henderson wrote: Ah, now I think I understand your problem. You want to `random' to generate random numbers that span all the possible values of the type within the range [0, 1], or at least a substantial subset, but the Real class doesn't let you generate any numbers other than integers. The above approach will give you random numbers from `random', but they will only ever be 0 or 1, so maybe they are not as random as you needed! ;-) Each pseudorandom generator generates a countable sequence of values, which is isomorphic to a sequence of integers. In good old (Turbo)C we got something between 0 and MAXINT and then divided by (double)MAXINT. Can't _this_ be done in Haskell? Of course it can be done, but not in class Real, you have to be in Fractional. I'm not sure why Real would be the class of choice for this problem anyway. I'd think that Fractional or RealFrac would be more appropriate. -- Lennart ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: type classes and generality
Hi All, Lennart Augustsson wrote: Each pseudorandom generator generates a countable sequence of values, which is isomorphic to a sequence of integers. In good old (Turbo)C we got something between 0 and MAXINT and then divided by (double)MAXINT. Can't _this_ be done in Haskell? Of course it can be done, but not in class Real, you have to be in Fractional. I'm not sure why Real would be the class of choice for this problem anyway. I'd think that Fractional or RealFrac would be more appropriate. I apologize for ignorance, I probably did not read this part of the doc attentively. But informally, the word 'Real' is widely used to denote a completely ordered field, and there is a theorem to change 'a' to 'the'. It's counterintuitive to use Real in any other meaning, I think. Alexander ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: type classes and generality
Alexander V. Voinov wrote: Hi All, Lennart Augustsson wrote: Each pseudorandom generator generates a countable sequence of values, which is isomorphic to a sequence of integers. In good old (Turbo)C we got something between 0 and MAXINT and then divided by (double)MAXINT. Can't _this_ be done in Haskell? Of course it can be done, but not in class Real, you have to be in Fractional. I'm not sure why Real would be the class of choice for this problem anyway. I'd think that Fractional or RealFrac would be more appropriate. I apologize for ignorance, I probably did not read this part of the doc attentively. But informally, the word 'Real' is widely used to denote a completely ordered field, and there is a theorem to change 'a' to 'the'. It's counterintuitive to use Real in any other meaning, I think. I agree. -- Lennart ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Type classes
A couple of people have asked about: [2] W Burton, E Meijer, P Sansom, S Thompson, P Wadler, "A (sic) extension to Haskell 1.3 for views", sent to the Haskell mailing list 23 Oct 1996 I am enclosing a copy of the "(sic)" proposal below. In light of Simon's proposal, the "(sic)" proposal should now be seen as a source of examples, rather than a still viable proposal. I agree with Phil Wadler: I think Heribert Schuetz makes a good argument that Simon's proposed notation would work better if adapted to the Maybe monad. Simon's original proposal struck me as something of a hack, whereas Schuetz's variant seems more disciplined. -- P I note that the "Maybe" approach allows nesting (via ++), which overcomes even the fairly obscure advantage of views noted by Simon. It also appears that the optimization of pattern-matching as given by Phil Wadler, in Chapter 5 of "The Implementation of Functional Programming Languages", by Simon Peyton Jones, can be easily expressed as a source to source translation, if the Maybe monad is used. On the other hand, given that we can hand translate all this into Haskell 1.4, I am also reasonable happy with Simon's original proposal (where the Just's are not explicitly given). The original proposal handles the vast majority of situations with less syntax. Finally, a couple of people have wondered whether the new guard syntax should be extended to other monads (perhaps with a now subclass with a fromMonad operator). The generalization of list comprehensions was cited as a precedent. Some members of the Haskell 1.4 Committee had second thought about general monad comprehensions after we saw some of the problems this caused. I don't think we want to generalize the guard notation to monads other than Maybe. All we would get for our efforts are additional obscure error messages, and we have enough of these already. Warren X-Sender: [EMAIL PROTECTED] Mime-Version: 1.0 Date: Wed, 23 Oct 1996 12:41:54 -0700 To: [EMAIL PROTECTED] From: [EMAIL PROTECTED] (F. Warren Burton) Subject: Views in Haskell Cc: [EMAIL PROTECTED], [EMAIL PROTECTED], [EMAIL PROTECTED], [EMAIL PROTECTED], [EMAIL PROTECTED] A proposal to extend Haskell 1.3 to support views follows. It is of course too late to consider this as an addition to Haskell 1.3. (Furthermore, with the addition of view it would be hard to justify continued support for our beloved n+k patterns.) Hence, this should be considered a proposal for a common extension to Haskell 1.3, or whatever John is currently calling these things. The objective of the proposal is to support pattern matching in the context of abstract datatype. Run-time overheads should be minimal. In particular, it should be possible for a compiler to implement views in such a way that, in the case where the concrete representation and the view defined for pattern matching are isomorphic, no additional run time costs are introduced because a program makes use of data abstraction. Values with viewtypes are constructed only at the time when pattern matching is applied to the resulting value, making it possible to completely optimize away the actual construction in simple cases such as this. Some problems (or at least complications) with previous proposals for views and Miranda laws are avoided by providing view transformations in only one direction. Views may be used in pattern matching but not in the construction of values. Hence, pattern matching with views should be considered a syntactic bundling of case selection and component extraction, rather than a syntactic mechanism for inverting construction. Since ordinary functions can be used to construct values having abstract datatypes, this is not a problem. An added advantage of this approach is that views may be used to capture some but not all the information that a value contains. The proposal is given in the form of changes to the Haskell 1.3 definition. Following the proposal is some additional discussion with additional examples. You may want to look at some of the examples before reading the proposal proper. A EXTENSION TO HASKELL 1.3 FOR VIEWS Proposed by Warren Burton, Erik Meijer, Patrick Sansom, Simon Thompson and Phil Wadler SYNTAX -- 1. "view" is a reserved word. 2. The following production is added to the Haskell 1.3 context free syntax: topdecl - "view" [context =] simpletype "of" type = constrs "where" valdefs 3.17.2 Informal Semantics of Pattern Matching (changes) -- - -- --- Add the following: 4. (d) Matching a non- _|_ value against a pattern whose outermost component is a constructor defined by view proceeds as follows. First, the view transformation for the view of the constructor is applied to the