- Haskell-Cafe - Haskell.org

RE: GHC Error Message.
by Simon Peyton-Jones 10 Mar '03

10 Mar '03

------------------------------------------------------------------------ --------------------------- data AParser String = AP {apapply::([String]->[(String,[String])])} Whoa! You can't declare a data type like that! You must have a type variable after the data type name, thus: data AParser a = AP .... It's an egregious bug that GHC does not reject your data type declaration. After that, all bets are off. Some deeply-wired-in invariant is not being obeyed, and all manner of bad things may happen. Thank you for showing up the bug -- I'll fix it. Simon

1 0

GHC Error Message.
by Mansour Al-Mutairi 09 Mar '03

09 Mar '03

Hi, Could someone please explain to me why the following error message happen: When I load the following code into GHC I get an error message: code: --------------------------------------------------------------------------------------------------- data AParser String = AP {apapply::([String]->[(String,[String])])} instance Monad AParser where return v = AP (\inp -> [(v,inp)]) (AP p) >>= f = AP (\inp -> concat [ apapply (f v) inp1 | (v,inp1) <- p inp]) --------------------------------------------------------------------------------------------------- error: --------------------------------------------------------------------------------------------------- Inferred type is less polymorphic than expected Quantified type variable `b' is unified with another quantified type variable `a' When trying to generalise the type inferred for `>>=' Signature type: forall a1 b1. AParser a1 -> (a1 -> AParser b1) -> AParser b1 Type to generalise: forall a1 b1. AParser a1 -> (a1 -> AParser b1) -> AParser b1 In the instance declaration for `Monad AParser' Failed, modules loaded: none. --------------------------------------------------------------------------------------------------- But when I create the type synonym type Stack = [String] data AParser String = AP {apapply::(Stack -> [(String,Stack)])} and use Stack instead of [String], GHC does not complain??? Thanks. Mansour.

1 0

Re: speedup help
by oleg＠pobox.com 08 Mar '03

08 Mar '03

| comb is only called from here: | sumbn n = sum [ bernoulli i * fromIntegral(comb (n+1) i) | i | <- [0 .. n-1] ] Probably I misunderstand what "bernoulli i" stands for. If it is meant Bernoulli number B_i, http://mathworld.wolfram.com/BernoulliNumber.html then the above expression is quite inefficient. Bernoulli numbers with odd indices are all zero, except B_1, which is -1/2. Therefore, the above expression ought to be written as sumbn n = 1 - (fromIntegral (n+1)%(fromIntegral 2)) + sum [ (b' i) * fromIntegral(comb (n+1) i) | i <- [2,4 .. n-1] ] It appears that you compute the sumbn to obtain B_n from the equality sum [bernoulli i * (comb (n+1) i) | i<-[0..n]] == 0 Have you tried bernoulli n = sum [ (sumib k n) % (k+1) | k<-[1..n]] where sumib k n = sum [ (comb k r) * r^n | r<-[2..k]] - sum [ (comb k r) * r^n | r<-[1,3..k]] the advantage of the latter series is that sumib is an Integer, rather than a rational. The powers of r can be memoized. Here's the code -- powers = [[r^n | r<-[1..]] | n<-[1..]] powers = [1..] : map (zipWith (*) (head powers)) powers -- neg_powers = [[(-1)^r * r^n | r<-[1..]] | n<-[1..]] neg_powers = map (zipWith (\n x -> if n then x else -x) (iterate not False)) powers pascal:: [[Integer]] pascal = [1,1] : map (\line -> zipWith (+) (line++[0]) (0:line)) pascal bernoulli n = sum [ fromIntegral (sumib k n) % fromIntegral (k+1) | k<-[1..n]] sumib:: Int -> Int -> Integer sumib k n = sum $ zipWith (*) (neg_powers!!(n-1)) (tail $ pascal!!(k-1)) This code seems to compute 'bernoulli 82' in less then a second, in Hugs (on a 2GHz Pentium IV).

4 6

RE: instance declaration troubles
by Simon Peyton-Jones 07 Mar '03

07 Mar '03

It's in 7.3.5.3. I'm going to make it more prominent S | -----Original Message----- | From: Hal Daume III [mailto:hdaume@ISI.EDU] | Sent: 07 March 2003 15:08 | To: Nick Name | Cc: Haskell Cafe | Subject: RE: instance declaration troubles | | Double Argh! I just noticed that this isn't what I meant to quote and now | I can't find it. But the basic idea of what I wanted to quote was that: | | YOu have to have at least one non-type variable in instance declarations | otherwise we don't necessarily know that reduction will terminate. I.e.: | | instance A a => B a where | instance B a => A a where | | will not terminate if you ever try to reduce A to B. I recall from the | docs that Simon is "looking for a rule which lifts this rule but still | maintains decidability." or something along those lines. | | Sorry about that! | | - Hal | | -- | Hal Daume III | hdaume(a)isi.edu | "Arrest this man, he talks in maths." | www.isi.edu/~hdaume | | On Fri, 7 Mar 2003, Simon Peyton-Jones wrote: | | > Argh. The documentation is out of date, or rather, inconsistent. | > | > In Section 7.3.4 you'll see that GHC -fglasgow-exts lifts the | > restriction that class methods must not constrain only the class type | > variable. | > | > I'll fix 7.3.5.2, which you are quoting. | > | > Simon | > | > | -----Original Message----- | > | From: Hal Daume III [mailto:hdaume@ISI.EDU] | > | Sent: 07 March 2003 03:16 | > | To: Nick Name | > | Cc: haskell-cafe(a)haskell.org | > | Subject: Re: instance declaration troubles | > | | > | From the GHC docs: | > | | > | In the signature of a class operation, every constraint must mention | > at | > | least one type variable that is not a class type variable. Thus: | > | | > | class Collection c a where | > | mapC :: Collection c b => (a->b) -> c a -> c b | > | | > | is OK because the constraint (Collection a b) mentions b, even though | > it | > | also mentions the class variable a. On the other hand: | > | | > | class C a where | > | op :: Eq a => (a,b) -> (a,b) | > | | > | is not OK because the constraint (Eq a) mentions on the class type | > | variable a, but not b. However, any such example is easily fixed by | > moving | > | the offending context up to the superclass context: | > | | > | class Eq a => C a where | > | op ::(a,b) -> (a,b) | > | | > | A yet more relaxed rule would allow the context of a class-op | > signature to | > | mention only class type variables. However, that conflicts with Rule | > | 1(b) for types above. | > | | > | -- | > | Hal Daume III | hdaume(a)isi.edu | > | "Arrest this man, he talks in maths." | www.isi.edu/~hdaume | > | | > | On Fri, 7 Mar 2003, Nick Name wrote: | > | | > | > | > | > I want to declare the following: | > | > | > | > class Get a where | > | > ls :: a b -> IO [b] | > | > mk :: IO [b] -> a b | > | > | > | > instance (Get a) => Functor a where | > | > fmap f x = mk (ls x >>= return . map f) | > | > | > | > | > | > But to have ghc type everything, I have to turn on "-fglasgow-exts | > | > -fallow-undecidable-instances -fallow-overlapping-instances". | > | > | > | > Is there a clean way to state that all types in my type class are | > also | > | > in the "Functor" type class? | > | > | > | > If not, what is the problem? | > | > | > | > Vincenzo | > | > _______________________________________________ | > | > Haskell-Cafe mailing list | > | > Haskell-Cafe(a)haskell.org | > | > http://www.haskell.org/mailman/listinfo/haskell-cafe | > | > | > | | > | _______________________________________________ | > | Haskell-Cafe mailing list | > | Haskell-Cafe(a)haskell.org | > | http://www.haskell.org/mailman/listinfo/haskell-cafe | > _______________________________________________ | > Haskell-Cafe mailing list | > Haskell-Cafe(a)haskell.org | > http://www.haskell.org/mailman/listinfo/haskell-cafe | > | | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

instance declaration troubles
by Nick Name 07 Mar '03

07 Mar '03

I want to declare the following: class Get a where ls :: a b -> IO [b] mk :: IO [b] -> a b instance (Get a) => Functor a where fmap f x = mk (ls x >>= return . map f) But to have ghc type everything, I have to turn on "-fglasgow-exts -fallow-undecidable-instances -fallow-overlapping-instances". Is there a clean way to state that all types in my type class are also in the "Functor" type class? If not, what is the problem? Vincenzo

2 4

RE: instance declaration troubles
by Simon Peyton-Jones 07 Mar '03

07 Mar '03

Argh. The documentation is out of date, or rather, inconsistent. In Section 7.3.4 you'll see that GHC -fglasgow-exts lifts the restriction that class methods must not constrain only the class type variable. I'll fix 7.3.5.2, which you are quoting. Simon | -----Original Message----- | From: Hal Daume III [mailto:hdaume@ISI.EDU] | Sent: 07 March 2003 03:16 | To: Nick Name | Cc: haskell-cafe(a)haskell.org | Subject: Re: instance declaration troubles | | From the GHC docs: | | In the signature of a class operation, every constraint must mention at | least one type variable that is not a class type variable. Thus: | | class Collection c a where | mapC :: Collection c b => (a->b) -> c a -> c b | | is OK because the constraint (Collection a b) mentions b, even though it | also mentions the class variable a. On the other hand: | | class C a where | op :: Eq a => (a,b) -> (a,b) | | is not OK because the constraint (Eq a) mentions on the class type | variable a, but not b. However, any such example is easily fixed by moving | the offending context up to the superclass context: | | class Eq a => C a where | op ::(a,b) -> (a,b) | | A yet more relaxed rule would allow the context of a class-op signature to | mention only class type variables. However, that conflicts with Rule | 1(b) for types above. | | -- | Hal Daume III | hdaume(a)isi.edu | "Arrest this man, he talks in maths." | www.isi.edu/~hdaume | | On Fri, 7 Mar 2003, Nick Name wrote: | | > | > I want to declare the following: | > | > class Get a where | > ls :: a b -> IO [b] | > mk :: IO [b] -> a b | > | > instance (Get a) => Functor a where | > fmap f x = mk (ls x >>= return . map f) | > | > | > But to have ghc type everything, I have to turn on "-fglasgow-exts | > -fallow-undecidable-instances -fallow-overlapping-instances". | > | > Is there a clean way to state that all types in my type class are also | > in the "Functor" type class? | > | > If not, what is the problem? | > | > Vincenzo | > _______________________________________________ | > Haskell-Cafe mailing list | > Haskell-Cafe(a)haskell.org | > http://www.haskell.org/mailman/listinfo/haskell-cafe | > | | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

debug with GHC FFI?
by paul＠theV.net 06 Mar '03

06 Mar '03

I am using Green Card to make some FFI modules with GHC, but sometimes it segfaults in the middle of nowhere, leaving no sensible stack trace in gdb. I wonder what is the proper way to debug FFI modules written in C? Trying to add a "-g" flag doesn't seem help at all... Regards, .paul.

1 1

You missed my Birthday again!
by Ami 06 Mar '03

06 Mar '03

Hi ya, Can't believe you missed my Birthday again, give me a call when you get this e-mail. You have to check out this great present Mel sent me, everyone at work is going mad over it! www.deals2go.co.uk/script Ami

1 0

Re: is identity the only polymorphic function without typeclasses?
by Jon Cast 04 Mar '03

04 Mar '03

Cagdas Ozgenc <co19(a)cornell.edu> wrote: > Greetings, > Is identity function the only meaningful function one can write > without constraining the type variable using a typeclass? If not, > could you please give a counter-example? Certainly you can write lots of ``meaningful function''s without type classes: not, (&&), (||), as well as many more complicated functions at more complicated types. You can also write useful polymorphic functions without type classes, as long as you specify at least one type. For example, you can write polymorphic functions over/yielding lists, such as repeat, cycle, map and its many relatives, foldr and its many relatives, take and its relatives, takeWhile and its relatives, etc. Similar functions often exist for other types. I'm somewhat curious, though: why do you ask this question? How do you expand your question that makes the answer seem to be ``no''? > Thanks Jon Cast

7 8

speedup help
by Damien R. Sullivan 04 Mar '03

04 Mar '03

So, I'm having to calculate 'n choose k' an awful lot. At the moment I've got this: comb :: Integer -> Integer -> Integer comb m 0 = 1 comb m n = (numerator(toRational (fact m) / toRational (fact n * fact (m-n)))) where fact is a memoized factorial function. It's not perfectly memoized, though; I use lists, since that's easier by default. They should be arrays, and possibly just changing that would speed comb up a lot. (Comb is currently 40% of runtime, fact is 23%.) But I think it should be possible to speed up comb itself, too. comb is only called from here: sumbn n = sum [ bernoulli i * fromIntegral(comb (n+1) i) | i <- [0 .. n-1] ] Here was one try: fcomb :: Integer -> Integer -> Integer fcomb m 0 = 1 fcomb m n = res where res = last * (m-n+1) `div` n last = res except, obviously, this doesn't work. I hope it's clear what I'm trying to do, or what I would be in a more imperative language -- in C I'd probably have some static variable in fcomb. I figure monads are needed, but I've been unable to figure them out enough to apply them here. Will the monadism propagate all the way up and require changing lots of function types? Bleah. I'm using ghc, can I sneak some mutable in here instead? Any advice? Also on using arrays, where my parameters come off the command line. I imagine in C++ I'd just precompute a bunch of tables and then just use those values in the actual algorithm. Thanks! -xx- Damien X-) (if you're curious, this is for a class, but not a class on using Haskell. I chose to use Haskell for this assignment after ghc -O, to my surprise, outperformed ocaml. I suspect GMP deserves the real credit, but hey.)

6 10