March 2004 - Haskell-Cafe

Context for type parameters of type constructors
by Henning Thielemann 03 Apr '04

03 Apr '04

Sorry for sending this twice, but it seems to me that the newsgroup fa.haskell only logs the discussion of haskell and haskell-cafe. ---------- Forwarded message ---------- Date: Mon, 29 Mar 2004 01:18:27 -0800 From: googlegroups(a)henning-thielemann.de (Henning Thielemann) Newsgroups: fa.haskell Subject: Context for type parameters of type constructors NNTP-Posting-Host: 134.102.210.249 Message-ID: <a17fb6f7.0403290118.786ede0d(a)posting.google.com> I have a problem with type classes that can be illustrated with the following example: I want to declare a class for vector like data. 'Vector' is not meant as a synonyme for 'array' but a 'vector' shall be a mathematical object that allows for some linear operations, namely summing and scaling. Thus I setup a type constructor VectorSpace in the following way: > module VectorSpace > where > > class VectorSpace v where > zero :: v a > add :: v a -> v a -> v a > scale :: a -> v a -> v a I haven't added context requirements like (Num a) to the signatures of 'zero', 'add', 'scale' because I cannot catch all requirements that instances may need. The problematic part is the 'scale' operation because it needs both a scalar value and a vector. Without the 'scale' operation 'v' could be simply a type (*) rather than a type constructor (* -> *). Now let's try some instances: > data (Num a) => VList a = VList [a] > > instance VectorSpace VList where > zero = VList (repeat 0) > add (VList x) (VList y) = VList (zipWith (+) x y) > scale s (VList x) = VList (map (s*) x) > > data (Num a) => VFunc b a = VFunc (b->a) > > instance VectorSpace (VFunc b) where > zero = VFunc (\_ -> 0) > add (VFunc f) (VFunc g) = VFunc (\x -> (f x) + (g x)) > scale s (VFunc f) = VFunc (\x -> s*(f x)) But now GHC complains: $ ghc -c VectorSpace.lhs VectorSpace.lhs:37: Could not deduce (Num a) from the context (VectorSpace VList) arising from the literal `0' at VectorSpace.lhs:30 Probable fix: Add (Num a) to the class or instance method `zero' In the first argument of `repeat', namely `0' In the first argument of `VList', namely `(repeat 0)' In the definition of `zero': zero = VList (repeat 0) ... I hoped that when I declare VList within the context (Num a) then it is always asserted that a VList is built on a Num type. If it is necessary to add (Num a) somewhere in the instance declaration - then where? Btw. I'm using $ ghc --version The Glorious Glasgow Haskell Compilation System, version 6.0

2 4

Adding Ord constraint to instance Monad Set?
by S. Alexander Jacobson 01 Apr '04

01 Apr '04

Following the declaration of "instance Monad []" in the prelude, and puzzling over the absence of its equivalent from Data.Set, I naively typed: instance Monad Set where m >>= k = concatSets (mapSet k m) return x = unitSet x fail s = emptySet concatSets sets = foldl union emptySet (setToList sets) instance (Eq b,Ord b) => Ord (Set b) where compare set1 set2 = compare (setToList set1) (setToList set2) and got the following error: Could not deduce (Ord b) from the context (Monad Set) arising from use of `concatSets' at dbMeta3.hs:242 Probable fix: Add (Ord b) to the class or instance method `>>=' In the definition of `>>=': >>= m k = concatSets (mapSet k m) In the definition for method `>>=' In the instance declaration for `Monad Set' Since I obviously can't modify the class declaration for Monad, the question arises: How does one add (Orb b) to the instance method '>>='? (Aside: it be really nice if the error messages suggested textual changes or at least provide sample syntax in addition to the conceptual recommendation.) -Alex- PS I assume the reason that Set is not declared as a Monad in Data.Set is oversight rather than incompatibility.... PPS I want to thank everyone who has been taking the time to answer all of my questions. I'll try to collect my various learnings into a useful beginners page once I reach the point where I think I can create a useful document. _________________________________________________________________ S. Alexander Jacobson mailto:me@alexjacobson.com tel:917-770-6565 http://alexjacobson.com

5 8

Re: [Haskell-cafe] Adding Ord constraint to instance Monad Set?
by MR K P SCHUPKE 31 Mar '04

31 Mar '04

>My intention was that the context before a data constructor shall mean that >the variable (a) shall be constrained only in the type of the constructor >function, not in the type definition. Okay, functional laguages have the notion that binding a variable is true for all time (like in mathematics)... Therefore if "a" is "1" then it has type Integer - forever. In this case the type of a in the first definition is "forall a . Num a". This is true for all references to a where we mean the same a. Because a is on the left-hand-side of the equals we assume all a's on the right are the same (it is the only rational choise) and hence we end up with two different types for a single variable. you could say something like (this doesn't work by the way) data Either a = (forall a . Num a => Left a) (forall a . Ord a => Right a) But here the a in each set of brackets has nothing to do with the a on the left hand side. This is different from: (data Either a = Num a => Left a | Ord a => Right a) where it is clear a == a but Ord a /= Num a Doing anything different would break the scoping rules for variables, and it is much more important IMHO to keep these consistant. Good languages are: Consistant, Symmetric, and Complete. Regards, Keean.

1 0

Re: [Haskell-cafe] Adding Ord constraint to instance Monad Set?
by MR K P SCHUPKE 31 Mar '04

31 Mar '04

> data Either a =3D > Num a =3D> Left a > Ord a =3D> Right a This is a mistake because the same variable is being constrained in two different ways. The only way both constrains can be satisfied is if a is both in Num and Ord. This can be written: data (Num a,Ord a) => Either a = Left a | Right a Which makes it a lot clearer that the constaints apply to both the Left and Right constructor. You have to remember that a is a polymorphic variable... now the first line [Num a => Left a] says that a has the type (forall a . Num a) but the second line [Ord a => Right a] says a has the type (forall a . Ord a) These are not the same type, so when they are combined (remember a scopes over the whole type definition) there is a type error because: (forall a . Ord a) is not the same as (forall a . Num a) Regards, Keean.

2 1

Re: Set Monad Problem...
by MR K P SCHUPKE 31 Mar '04

31 Mar '04

Okay, what is wrong with using a State Monad where the state is a Set. You can then define additional functions to insert etc. Regards, Keean.

1 0

RE: [Haskell-cafe] Adding Ord constraint to instance Monad Set?
by Simon Peyton-Jones 31 Mar '04

31 Mar '04

| > bindSet :: forall a b. (Ord a, Ord b) | > => T a -> (a -> T b) -> T b | | To translate the question from my problem to this one: | What would be if Set would be declared within Ord context, i.e. | data (Ord a) => Set a = ... | ? Now it would be safe to use Set as Monad because Sets could only | constructed from Ord types. No, the same problem arises. You could imagine that every Set contains its Ord methods. Then bind wouldn't need to pass them. But return :: Monad a => a -> m a The Set instance would have to be unitSet :: a -> Set a Where does the Ord dictionary come from? No, this won't work. Some of this stuff is discussed in a very old paper of mine http://research.microsoft.com/%7Esimonpj/Papers/classhask.ps.gz But I can't promise it covers this particular issue, and it predates functional dependencies. | "Constraints on datatype declarations are a misfeature of Haskell, and | have no useful effect." | | Is this the final conclusion? Yes, it is, I believe. Constraints on data type declarations are a mis-feature. I tried to get them removed, but there was some argument that they could be made useful (see John Hughes's paper "Restricted data types in Haskell", Haskell workshop 1999), and they stayed. Simon

2 1

Re: [Haskell-cafe] Adding Ord constraint to instance Monad Set?
by MR K P SCHUPKE 31 Mar '04

31 Mar '04

>This syntax would also have the advantage that you can apply different >contexts to different constructors. Er, you can already do that as I just pointed out: data (Ord a,Num b) => Either a b = Left a | Right b Note that to constrain the same type variable differently for different constructors would be a type error. In other words this: data Either a = Num a => Left a Ord a => Right a Is not valid, because (forall a . Num a) is not the same type as (forall a . Ord a). So infact the current way of writing it as data (Num a) => Either a = Left a | Right a Is better because it does not allow you to make that mistake. Regards, Keean.

2 1

RE: [Haskell-cafe] Adding Ord constraint to instance Monad Set?
by MR K P SCHUPKE 31 Mar '04

31 Mar '04

| "Constraints on datatype declarations are a misfeature of Haskell, and | have no useful effect." |=20 | Is this the final conclusion? >Yes, it is, I believe. Constraints on data type declarations are a >mis-feature. I tried to get them removed, but there was some argument >that they could be made useful Might I try and pursuade you that mis-feature is a bit strong. A data type declaration creates two things - the data type itself and the constructor function. If you consider the constrains in the data type declaration to apply only to the constructor then it all makes sense. functions do not infer constrains from enclosed functions, for example: fna :: Num a => a -> a fna a = -a fnb :: a -> a fnb a = fna a In this case fna has a type error, the function is declared without the required Num a constraint. This is the same for data constructors, consider: data Num a => MyList a = MyList [a] This means that the constuctor for mylist has the (Num a) constraint. Simple! This is not a misfeature - more a mis-understood feature. So, using: print $ MyList ['a','b','c'] -- fails: No instance for (Num Char) print $ MyList [1,2,3] -- is Okay. and unexpectedly a use of the constructor does not get the constraint: fnc :: a -> MyList a fnc a = MyList [a] -- fails: Could not deduce (Num a) from the context () But if you consider the constructor to be just like a normal function this is perfectly consistant. This should definitely not be removed, as there is no other way to apply a constaint to a constructor function. Regards, Keean.

3 2

RE: [Haskell-cafe] Adding Ord constraint to instance Monad Set?
by MR K P SCHUPKE 31 Mar '04

31 Mar '04

But that is already used for existential datatypes: data Test = forall a . Num a => Test a Maybe that lack of forall is enough to distinguish the two though. Your example would currently be written: data (Ord a,Num b) => Either a b = Left a | Right b I dont have any problem with this, just remember these are constraints on function arguments... It my superficially look like a class system, but in reality it is more like a constraint based programming language (for example Prolog) at the type level... Regards, Keean.

1 0

RE: [Haskell-cafe] Adding Ord constraint to instance Monad Set?
by Simon Peyton-Jones 31 Mar '04

31 Mar '04

Alex | Following the declaration of "instance Monad []" | in the prelude, and puzzling over the absence of | its equivalent from Data.Set, I naively typed: | | instance Monad Set where | m >>= k = concatSets (mapSet k m) | return x = unitSet x | fail s = emptySet | | concatSets sets = foldl union emptySet (setToList sets) | instance (Eq b,Ord b) => Ord (Set b) where | compare set1 set2 = compare (setToList set1) (setToList set2) | | and got the following error: | | Could not deduce (Ord b) from the context (Monad Set) | arising from use of `concatSets' at dbMeta3.hs:242 I'm sorry to say that you just can't make Set an instance of Monad. To make an instance of Monad for a type constructor T you must have a function bindT :: forall a b. T a -> (a -> T b) -> T b And there just *is* no such function for Set, because of the need for ordering. There's a less polymorphic function bindSet :: forall a b. (Ord a, Ord b) => T a -> (a -> T b) -> T b To see why this is no good, consider sequence :: Monad m => [m a] -> m [a] The code for sequence calls (>>=) a lot. You can't supply bindSet as the function to call because bindSet takes two Ord parameters at run-time, whereas ordinary bind does not. It's not just a quirk of the type system -- there is a real problem! Simon

3 2