How to properly define an Haskell function isPrime?

Question

I'm trying to create a basic function to test primality of an integer in Haskell. I have code which will work in an ad hoc sense, but continue to get an error message when I try to pass it to a function. Note that I'm writing the definitions directly in GHCi, using :{ and :}.

The idea is to create a list of N modulo {all integers up to a rounded sqrt (N)}, and then test the resulting list for a zero other than the initial index. The following four functions all work:

rndRoot :: (Floating a, Integral c, RealFrac a) => a -> c
rndRoot = round . sqrt

oneToRndRoot :: (Floating a, Integral t, RealFrac a) => a -> [t]
oneToRndRoot x = [1..rndRoot(x)]

modulo x y
  | n < 0 = x
  | otherwise = modulo n y
  where n = x - y

mapMod x = map (modulo x)

This also works:

mapMod 49 (oneToRndRoot 49)

However, while the repl accepts this definition without complaint...

mapModToRndRoot x = mapMod x $ oneToRndRoot x

... it spits out the following error message when I try to use it:

Prelude> mapModToRndRoot 39

<interactive>:475:1:
    No instance for (Floating a0) arising from a use of ‘it’
    The type variable ‘a0’ is ambiguous
    Note: there are several potential instances:
      instance Floating Double -- Defined in ‘GHC.Float’
      instance Floating Float -- Defined in ‘GHC.Float’
    In the first argument of ‘print’, namely ‘it’
    In a stmt of an interactive GHCi command: print it

The ad hoc solution which seems to work fine is just to use two arguments rather than repeat the same one

mapModToRndRoot2 x y = map (modulo x) (oneToRndRoot y)

Prelude> mapModToRndRoot2 33 33
[0,1,0,1,3,3]

Which version of GHC you are using? I'm asking because I get slightly different errors from yours. The `let`s in the GHCi input that were in the original version of the question (and that I have edited away...) might suggest you aren't using GHC 8. — duplode, Mar 16 '18 at 04:07
While it is a good idea to upgrade if you can, note you'll still have the same problem, as explained by Fried Brice, only with a different error message. (I only asked about the GHC version to make sure I wouldn't be missing any details that might be relevant when writing an answer.) — duplode, Mar 16 '18 at 06:25
For efficiency you might better avoid switching between integers and floating point by replacing the condition $n<=sqrt(x)$ by $n^2<=x$ in oneToRndRoot. There is a function called takeWhile that can help you to select the integers from [1..] fulfilling this condition. — j.p., Mar 16 '18 at 07:50

Fried Brice · Answer 1 · 2018-03-16T22:25:49.740

Inspecting the type of mapModToRndRoot give the following:

mapModToRndRoot :: (Floating a, Integral a, RealFrac a) => a -> [a]

So, to call mapModToRndRoot 39, we'd need to assign a numeric type to the literal 39 that is an instance of RealFrac, Integral, and Floating. However, none of the Prelude numeric types satisfy all three of those constraints, so we get a compile error.

On the other hand, mapMod 49 (oneToRndRoot 49) works just fine. Notice the type of the below lambda:

\x y -> mapMod x (oneToRndRoot y)
  :: (RealFrac a, Integral b, Floating a) => b -> a -> [b]

By using two literals, GHC is able to assign different types to each of them in order to satisfy the type class constrains.

Edit: Here is a solution suggested by @duplode:

rndRoot :: (Integral a) => a -> a
rndRoot = round . sqrt . fromIntegral

My original suggestion fromIntegral . round . sqrt is susceptible to all the usual wonkiness that comes with using floating point arithmetic.

Edit: As @WarrickMacmillan points out, the signature of oneToRndRoot must also be changed. Below is the entire working program fully annotated.

rndRoot :: Integral a => a -> a
rndRoot = round . sqrt . fromIntegral

oneToRndRoot :: Integral a => a -> [a]
oneToRndRoot x = [1..rndRoot(x)]

modulo :: (Ord p, Num p) => p -> p -> p
modulo x y
  | n < 0 = x
  | otherwise = modulo n y
  where n = x - y

mapMod :: (Num b, Ord b) => b -> [b] -> [b]
mapMod x = map (modulo x)

mapModToRndRoot :: Integral a => a -> [a]
mapModToRndRoot n = mapMod n (oneToRndRoot n)

Your diagnostic is spot on, but there is a better solution: `rndRoot = round . sqrt . fromIntegral`. With that, the OP won't need to change the types of the other functions, nor to switch from integer arithmetic to floating point arithimetic (with all the convenience and correctness issues that might bring -- in particular, a Haskell-specific complication is that [floating-point ranges are generally a bad idea](https://stackoverflow.com/q/7290438/2751851)). — duplode, Mar 16 '18 at 06:16
I had just let it infer the types orignally and then added it to my code, so I will be sure specify this from now on. For anyone else, the type signature for oneToRndRoot should also reflect this change `oneToRndRoot :: (Integral a) => a -> [a]` `oneToRndRoot x = [1..rndRoot(x)]` — , Mar 16 '18 at 21:59

How to properly define an Haskell function isPrime?

1 Answers1