CODEWITHSUNDEEP
haskell
manuzhang
manuzhang

Reputation: 3025

haskell type signature for integers

Say I want to write a function to decide whether a given integer number is prime, which type signature should I use?

  isPrime :: Int -> Bool

or 

  isPrime :: (Integral a) => a -> Bool

What's the difference? Is there a particular reason to choose one over the other?
If so, in which situations should I use the two respectively?

Upvotes: 10

Views: 1617

Answers (3)

Daniel Fischer
Daniel Fischer

Reputation: 183888

I would recommend the signature

isPrime :: Integer -> Bool

A signature isPrime :: Int -> Bool would exclude fast tests for largish numbers, since those tests would often overflow then (technically that is also true of Integer, at least in the version provided by integer-gmp, but you will most likely be out of memory long before that matters, so we can maintain the fiction of an infinite Integer type).

A type isPrime :: Integral a => a -> Bool would be a lie with any feasible implementation. One could have an instance of Integral for a type modeling Z[sqrt(2)] (though for such a type toInteger would be unfaithful), for such a type, 2 would not be a prime, how would one detect that with a generic test?

Or consider finite types modeling a factor ring Z/(n). An Ord instance for such types would be incompatible with the arithmetic, but we already have that for Int etc. For example, in Z(6) = {0,1,2,3,4,5}, the primes would be 2, 3 and 4 (note that none of them is irreducible, 2 = 4*2, 3 = 3*3, 4 = 2*2).

So the only meaningful and feasible test is, "is it a rational (or natural) prime whose value happens to be in the range of the type?". That is captured (as good as possible without sacrificing too much speed) in the type isPrime :: Integer -> Bool, to be combined with a toInteger when appropriate.

Upvotes: 4

ertes
ertes

Reputation: 11

Many primality tests are probabilistic and need random numbers, so at least at the lowest level they would have a type signature like this:

seemsPrime :: (Integral a) => a -> [a] -> Bool

An Integral constraint seems reasonable, because usually you do not need a concrete type, but only operations like rem.

Upvotes: 1

C. A. McCann
C. A. McCann

Reputation: 77384

The type Int -> Bool means that your function operates on values of type Int, which are size-limited integers (the maximum size being, I believe, machine-dependent).

The type (Integral a) => a -> Bool means that your function operates on values of any type that has an instance of the Integral type class--i.e., types that behave like integers in a particular way. The main reason to chose this over a concrete type is to create a more general-purpose function.

Generic forms using Integral tend to be most useful when you need to work with integer-like types in other contexts--a good example being places where the standard library fails to do so, e.g. functions like replicate :: Int -> a -> [a]. Code that operates on some specific integer-like type for its own purposes that wants to use that type with replicate therefore needs to convert to Int first, or import genericReplicate from Data.List.

What you might want to consider in your case is instead the type Integer, which represents integers of arbitrary size. Since your main goal is the calculation, there's less value to supporting arbitrary integral types.

If memory serves me, the only instances of Integral in the standard library are Int and Integer anyhow. (EDIT: As hammar reminds me in the comments, there are also instances for fixed-size types in Data.Int and Data.Word. There are also foreign types like CInt but I was disregarding those intentionally.)

Upvotes: 11

Related Questions