Difference between `(Integer a) => a -> Bool` and ` Integer -> Bool`?

Question

I wrote my first program in Haskell today. It compiles and runs successfully. And since it is not a typical "Hello World" program, it in fact does much more than that, so please congrats me :D

Anyway, I've few doubts regarding my code, and the syntax in Haskell.

Problem:

My program reads an integer N from the standard input and then, for each integer i in the range [1,N], it prints whether i is a prime number or not. Currently it doesn't check for input error. :-)

Solution: (also doubts/questions)

To solve the problem, I wrote this function to test primality of an integer:

is_prime :: Integer -> Bool
is_prime n = helper n 2
        where
          helper :: Integer -> Integer -> Bool
          helper n i  
              | n < 2 * i = True
              | mod n i > 0 = helper n (i+1)
              | otherwise = False

It works great. But my doubt is that the first line is a result of many hit-and-trials, as what I read in this tutorial didn't work, and gave this error (I suppose this is an error, though it doesn't say so):

prime.hs:9:13:
    Type constructor `Integer' used as a class
    In the type signature for `is_prime':
      is_prime :: Integer a => a -> Bool

According to the tutorial (which is a nicely-written tutorial, by the way), the first line should be: (the tutorial says (Integral a) => a -> String, so I thought (Integer a) => a -> Bool should work as well.)

is_prime :: (Integer a) => a -> Bool

which doesn't work, and gives the above posted error (?).

And why does it not work? What is the difference between this line (which doesn't work) and the line (which works)?

---

Also, what is the idiomatic way to loop through 1 to N? I'm not completely satisfied with the loop in my code. Please suggest improvements. Here is my code:

--read_int function
read_int :: IO Integer
read_int = do
     line <- getLine
     readIO line

--is_prime function
is_prime :: Integer -> Bool
is_prime n = helper n 2
        where
          helper :: Integer -> Integer -> Bool
          helper n i  
              | n < 2 * i = True
              | mod n i > 0 = helper n (i+1)
              | otherwise = False

main = do
       n <- read_int
       dump 1 n
       where
           dump i x = do 
                 putStrLn ( show (i) ++ " is a prime? " ++ show (is_prime i) )
                 if i >= x 
                    then putStrLn ("")
                  else do
                    dump (i+1) x

Answer 1

You are misreading the tutorial. It would say the type signature should be

is_prime :: (Integral a) => a -> Bool
--       NOT Integer a

These are different types:

• Integer -> Bool
  • This is a function that takes a value of type Integer and gives back a value of type Bool.
• Integral a => a -> Bool
  • This is a function that takes a value of type a and gives back a value of type Bool.
  • What is a? It can be any type of the caller's choice that implements the Integral type class, such as Integer or Int.

(And the difference between Int and Integer? The latter can represent an integer of any magnitude, the former wraps around eventually, similar to ints in C/Java/etc.)

---

The idiomatic way to loop depends on what your loop does: it will either be a map, a fold, or a filter.

Your loop in main is a map, and because you're doing i/o in your loop, you need to use mapM_.

let dump i = putStrLn ( show (i) ++ " is a prime? " ++ show (is_prime i) )
 in mapM_ dump [1..n]

Meanwhile, your loop in is_prime is a fold (specifically all in this case):

is_prime :: Integer -> Bool
is_prime n = all nondivisor [2 .. n `div` 2]
        where
          nondivisor :: Integer -> Bool
          nondivisor i = mod n i > 0

(And on a minor point of style, it's conventional in Haskell to use names like isPrime instead of names like is_prime.)

Answer 2

Part 1: If you look at the tutorial again, you'll notice that it actually gives type signatures in the following forms:

isPrime :: Integer -> Bool
-- or
isPrime :: Integral a => a -> Bool
isPrime :: (Integral a) => a -> Bool -- equivalent

Here, Integer is the name of a concrete type (has an actual representation) and Integral is the name of a class of types. The Integer type is a member of the Integral class.

The constraint Integral a means that whatever type a happens to be, a has to be a member of the Integral class.

Part 2: There are plenty of ways to write such a function. Your recursive definition looks fine (although you might want to use n < i * i instead of n < 2 * i, since it's faster).

If you're learning Haskell, you'll probably want to try writing it using higher-order functions or list comprehensions. Something like:

module Main (main) where
import Control.Monad (forM_)

isPrime :: Integer -> Bool
isPrime n = all (\i -> (n `rem` i) /= 0) $ takeWhile (\i -> i^2 <= n) [2..]

main :: IO ()
main = do n <- readLn
          forM_ [1..n] $ \i ->
              putStrLn (show (i) ++ " is a prime? " ++ show (isPrime i))