CODEWITHSUNDEEP
haskellcompiler-errorsprimes
Christopher King
Christopher King

Reputation: 10941

Haskell prime number generator error

I tried:

composites=[c|c<-[4..], any (\p->(c`mod`p == 0)) (takeWhile (< (sqrt c)) primes)]
primes=2:[p|p<-[3..], not p `elem` (takeWhile (<p) composites)]

and got:

pad.hs:1:19:
    No instance for (Num Bool) arising from the literal `4'
    Possible fix: add an instance declaration for (Num Bool)
    In the expression: 4
    In the expression: [4 .. ]
    In a stmt of a list comprehension: c <- [4 .. ]

pad.hs:1:30:
    No instance for (Integral Bool) arising from a use of `divisible'
    Possible fix: add an instance declaration for (Integral Bool)
    In the first argument of `any', namely `(divisible c)'
    In the expression: any (divisible c) (factors c)
    In a stmt of a list comprehension: any (divisible c) (factors c)

pad.hs:3:43:
    No instance for (Floating Bool) arising from a use of `sqrt'
    Possible fix: add an instance declaration for (Floating Bool)
    In the second argument of `(<)', namely `sqrt c'
    In the first argument of `takeWhile', namely `(< sqrt c)'
    In the expression: takeWhile (< sqrt c) primes
Failed, modules loaded: none.

I think that it is confused as to what type of number it is dealing with, but I am not sure. Any tips?

Upvotes: 1

Views: 170

Answers (2)

Will Ness
Will Ness

Reputation: 71065

Any tips?

Well, now that you got it fixed,

composites=[c|c<-[4..], any ((==0).(c`mod`)) (takeWhile ((<= c).(^2)) primes)]
primes=2:[p|p<-[3..], not (p `elem` takeWhile (<= p) composites)]

consider whether you can make it faster. For one thing, elem fully consumes its second argument when the 1st isn't present in it, and always searches from the start. But if we've just searched for 16 among the composites, there's no need to start over when we search for 17 next - we can continue on from the same point:

notAmong (_, (k:ks,c:cs))              -- a candidate that is not among
   | k == c    = (Nothing, (ks,cs))    --     the composites, is a prime
   | otherwise = (Just k, (ks,c:cs))   -- (k < c)
primes = 2 : [p | (Just p,_) <- iterate notAmong (Just 3, ([4..],composites))]

We've fused the functions not, elem and takewhile, with great benefit speedwise.

Try to find out this version's empirical orders of growth and compare with the original version, it's fun.

Upvotes: 1

leftaroundabout
leftaroundabout

Reputation: 120711

I think that it is confused as to what type of number it is dealing with

Quite right! So why don't you tell it? It's always a good idea to write the function signature in Haskell, before the actual implementation. Not only does this prevent such confusing compiler messages when something's wrong, it also makes up a really good guide in actually designing the function.

So in your case, you probably want1

composites, primes :: [Integer]

which of course doesn't solve the problem, but it makes the error messages much clearer:

Prelude> let composites,primes::[Integer]; composites=[c|c<-[4..], any (\p -> c`mod`p == 0) (takeWhile (< sqrt c) primes)]; primes=2:[p|p<-[3..], not p `elem` (takeWhile (< p) composites)]

<‌interactive>:2:128:
    Couldn't match expected type `Integer' with actual type `Bool'
    In the expression: p
    In the second argument of `(:)', namely
      `[p | p <- [3 .. ], not p `elem` (takeWhile (< p) composites)]'
    In the expression:
      2 : [p | p <- [3 .. ], not p `elem` (takeWhile (< p) composites)]

<‌interactive>:2:169:
    Couldn't match type `Integer' with `Bool'
    Expected type: [Bool]
      Actual type: [Integer]
    In the second argument of `takeWhile', namely `composites'
    In the second argument of `elem', namely
      `(takeWhile (< p) composites)'
    In the expression: not p `elem` (takeWhile (< p) composites)

It's still not exactly to the point, but at least it now localises the error to where it is: in primes, p is inferred to be Bool, which is of course wrong. The reason for bool is that you have not p `elem` (...) in there. Evidently you think this is parsed as not (p`elem`(...)), but it's not: plain prefix function application has higher precedence than any infix operator. An important thing to know (that's also why you don't need parens around sqrt c in (< sqrt c)).

Let's fix that, then there remains one more problem:

Prelude> let composites,primes::[Integer]; composites=[c|c<‌-[4..], any (\p->(c`mod`p == 0)) (takeWhile (<‌ (sqrt c)) primes)]; primes=2:[p|p<‌-[3..], not $ p `elem` (takeWhile (<‌p) composites)]

<‌interactive>:3:99:
    No instance for (Floating Integer) arising from a use of `sqrt'
    Possible fix: add an instance declaration for (Floating Integer)
    In the second argument of `(<‌)', namely `(sqrt c)'
    In the first argument of `takeWhile', namely `(<‌ (sqrt c))'
    In the second argument of `any', namely
      `(takeWhile (<‌ (sqrt c)) primes)'

Now that is spot on: you're dealing with integer numbers, but sqrt obviously yields generally irrational numbers, so it only makes sense with a Floating type. To get around this, you can use the (admittedly ugly, but ok) sqrt' = round . sqrt . fromIntegral.

1Actually, this monomorphic signature is probably not ideal – you might prefer Int for various reasons (mainly efficiency). To be on the safe side, one would choose Integral a => [a]; however polymorphic values aren't "memoised" at the top level which is again quite a problem in this example.

Upvotes: 2

Related Questions