CODEWITHSUNDEEP
haskelldiscrete-mathematicsnumber-theory
user5775230
user5775230

Reputation:

How to properly define an Haskell function isPrime?

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]

Upvotes: 4

Views: 307

Answers (1)

Fried Brice
Fried Brice

Reputation: 780

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)

Upvotes: 4

Related Questions