CODEWITHSUNDEEP
haskelltypessqrt
Георги Лалев
Георги Лалев

Reputation: 73

Struggling with Haskell type system

I am trying to learn some Haskell by doing basic tasks in the particular case I am trying to implement some basic function for primality check, but I really can figure out the types, my code is

isPrime :: (Num a) => a -> Bool
isPrime n
    | n <= 1 = False
    | otherwise = not $ 0 `elem` map (mod n) [2..m] where m = floor $ sqrt n

I tried instead of (Num a) => a to use different number types or to use sqrt with fromIntegral but I still get error messages, like:

*Could not deduce (Floating a) arising from a use of `sqrt'
  from the context: Num a
    bound by the type signature for:
               isPrime :: forall a. Num a => a -> Bool
    at Helpers.hs:5:1-31
  Possible fix:
    add (Floating a) to the context of
      the type signature for:
        isPrime :: forall a. Num a => a -> Bool
* In the second argument of `($)', namely `sqrt n'
  In the expression: floor $ sqrt n
  In an equation for `m': m = floor $ sqrt n
| otherwise = not $ 0 `elem` map (mod n) [2..m] where m = floor $ sqrt n

I can really use some help here, thank you in advance.

Upvotes: 1

Views: 152

Answers (3)

Yann Vernier
Yann Vernier

Reputation: 15877

The issue the compiler is describing is that you're applying incompatible operations to the same type: mod requires Integral a, sqrt requires Floating a, and no type satisfies both. You could work around that using type conversions like fromIntegral and ceiling, but you'd want to be careful to avoid rounding errors. For my test, I removed the type constraint and used m = ceiling $ sqrt $ fromIntegral n, which led to the inferred type isPrimeSqrt :: Integral a => a -> Bool.

Another approach is to consider why the conflict was hit and look for other solutions. The reason for sqrt is to produce an optimized stopping point for the test. Can we find that stopping point in another manner?

As it turns out, while division is expensive, it frequently produces two results: the quotient and remainder. With mod you're looking for the latter, but we have divMod and quotRem which produce both. So it could be worth testing if that's notably slower than the plain mod test (benchmark results, comparing [2..] vs [2..m]). 

isPrime n = (n > 1) && null (filter isFactor (takeWhile notTooHigh divisors))
  where notTooHigh (divisor,quotient,_) = divisor <= quotient
        isFactor (_,_,remainder) = remainder == 0
        divisors = [(divisor,quotient,remainder) |
                    divisor <- 2:[3,5..],
                    let (quotient,remainder) = quotRem n divisor]

Upvotes: 1

Josh Ferrerra
Josh Ferrerra

Reputation: 41

As others have mentioned, the use of mod requires a to be Integral, and the use of sqrt requires a to be Floating. Judging by the name of your function, I'm assuming that you want to use it on integral types. So, you can fix this by changing your signature to isPrime :: (Integral a) => a -> Bool, then precomposing sqrt with fromIntegral. You could do something like

where m = floor . sqrt . fromIntegral $ n

Another option would be to replace [1..m] with something like takeWhile (\x -> x * x <= n) [1..] to avoid the need for Floating.

Upvotes: 4

bipll
bipll

Reputation: 11940

You have two problems in your code:

  1. Incompatible types.

Calling both sqrt n and (mod n) reqiure n to be both Floating and Integral at the same time.

  1. Insufficient context. Requiring only (Num a) does not allow neither of the operations.

A possible fix would be: a) narrow down type context to a much more concise (Integral a); b) add fromIntegral to sqrt's argument:

isPrime :: Integral a => a -> Bool
isPrime n
    | n <= 1 = False
    | otherwise = not $ 0 `elem` map (mod n) [2..m] where m = floor $ sqrt $fromIntegral n

Upvotes: 3

Related Questions