- Haskell-Cafe - Haskell.org

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

[Haskell-cafe] RE: [Haskell] Programming language shootout (completing theHaskell entry)
by Simon Marlow 31 Mar '04

31 Mar '04

> When compiling via gcc, there's the __builtin_prefetch function: > > http://gcc.gnu.org/onlinedocs/gcc-3.3.3/gcc/Other-Builtins.html > (about 2/3rds of the way down the page) Thanks, I wasn't aware of that. > see also: > http://gcc.gnu.org/projects/prefetch.html > > I didn't read it very carefully, but it's not clear (on the > x86 cpus) if > there is a prefetch instruction that is common between the amd & intel > flavours, ie would a ghc binary with prefetch be portable between > P3/P4/Athlon. P3/P4 and Athlon have different prefetch instructions. However, Athlon64 supports the P3/P4 instructions. Cheers, Simon

1 0

Re: [Haskell-cafe] Context for type parameters of type constructors
by MR K P SCHUPKE 30 Mar '04

30 Mar '04

>I didn't get the point yet why the context for 'data' >is not sufficient for the 'instance' method definition. Not sure who's relpy you're replying to, but I thought my response was pretty clear (I would though)... The problem is that to define 'zero' the type of the 'zero' must unify with the vector type. If you define vector operations as (v a) then a is a polymorphic variable. However the definition of zero implies that a is an Integral .. these are not the same type: (forall a . a) is not (forall a . Integral a => a) and thats where the type error comes from. You have two choices, drop the definition of zero, or use multi-parameter type classes. You could get rid of zero and have: class VectorSpace v where set :: Num a => a -> v a add :: Num a => v a -> v a -> v a scale :: Num a => a -> v a -> v a Should do the trick! (zero becomes "set 0") Regards, Keean.

3 3

What are Kind errors and how do you fix them?
by S. Alexander Jacobson 29 Mar '04

29 Mar '04

Implementing Reverse from before, I am running into this weird error: type ReverseType a string = (string ->(string,a)) data Reverse a string = Reverse (ReverseType a string) instance Monad (Reverse a s) where return x = Reverse (\text -> (text,x)) (Reverse p) >>= k = Reverse p3 where p3 s0 = p2 s1 where (Reverse p2) = k a (s1,a)=p s0 Produces the error: Kind error: Expecting kind `* -> *', but `Reverse a s' has kind `*' When checking kinds in `Monad (Reverse a s)' In the instance declaration for `Monad (Reverse a s)' I have no clue what this error message means. -Alex- _________________________________________________________________ S. Alexander Jacobson mailto:me@alexjacobson.com tel:917-770-6565 http://alexjacobson.com

5 6

Re: [Haskell-cafe] Context for type parameters of type constructors
by MR K P SCHUPKE 29 Mar '04

29 Mar '04

>Could not deduce (Num a) from the context (VectorSpace VList) The problem is in the definition: zero = VList (repeat 0) Is "0" an Int or an Integer? To define zero, instances need to be parameterised by vector type: EG: class VectorSpace v a where zero :: v a add :: v a -> v a -> v a scale :: a -> v a -> v a instance VectorSpace VList Int where zero = VList (repeat 0) ... instance VectorSpace VList Float where zero = VList (repeat 0.0) etc... >Could not deduce (Num a) from the context (VectorSpace VList) The problem is in the definition: zero = VList (repeat 0) Is "0" an Int or an Integer? To define zero, instances need to be parameterised by vector type: EG: class VectorSpace v a where zero :: v a add :: v a -> v a -> v a scale :: a -> v a -> v a instance VectorSpace VList Int where zero = VList (repeat 0) ... instance VectorSpace VList Float where zero = VList (repeat 0.0) etc... Regards, Keean.

1 0

RE: [Haskell-cafe] looking for optimization advice
by Simon Marlow 29 Mar '04

29 Mar '04

> I think that adding the extra check to see if the pointers > are identical > sped this up enough that it's probably no longer a major > issue--I'm pretty > certain that the problem was large strings that were > identical, so every > byte had to be checked, so probably scary non-portable home-made > ForeignPtrs would not be worth the effort. (Although I'm > somewhat curious as to how it would be done...) A ForeignPtr allocated with mallocForeignPtr in GHC is heap-allocated garbage-collectable storage, and doesn't need a finalizer. The other kind of ForeignPtr created with newForeignPtr is associated with some external storage and needs a finalizer. Finalizers are expensive, and so is malloc(), but mallocForeignPtr is very cheap. This gives rise to a sum-type in the implementation of ForeignPtr: see the source code (libraries/base/GHC/ForeignPtr.hs). You could make a specialised version by ripping out the non-malloc ForeignPtr bits, and make an unboxable ForeignPtr type. A mallocForeignPtr-style ForeignPtr is essentially the same as an IOUArray. In fact, the underlying implementation type is the same (MutableByteArray#), except that a ForeignPtr is allocated in pinned (immovable) storage so that it can be passed to foreign functions. There could easily be a conversion from a "malloc" ForeignPtr to IOUArray. There is also some overlap with the StorableArray type. A StorableArray has a ForeignPtr inside it. It really looks like the framework could be simplified here, but I remember putting some thought into it and not coming up with a simple solution. Cheers, Simon

1 0