[Haskell-cafe] I need help getting started

[Daniel Fischer]

Am Sonntag 25 April 2010 06:34:32 schrieb mitchell at kaplan2.com:

Luke already explained the type error, so I'll focus on the implementation.

> Hi,
>
>
>
> I'm just starting to learn, or trying to learn Haskell.  I want to write
> a function to tell me if a number's prime.  This is what I've got:
>
>
>
> f x n y = if n>=y

Since you call it with y = floor (sqrt (fromIntegral x)),
the test ought to be "n > y" or you'll classify squares of primes as 
primes.

PrimeTest> primeQ 25
True

Oops.

>           then True
>           else
>           if gcd x n == 1

This is doing a lot of unnecessary work.
If gcd x n > 1, then one of the prime divisors of n must also divide x.
If n is composite, this test is never reached, otherwise (n is prime) n 
divides x, so you need only test whether n divides x,
   
         if x `rem` n /= 0

This test needs only one division, whereas calculating the gcd needs 
O(log n) divisions on average. For larger primes, that's a big difference:

Prelude PrimeTest> primeF 1000000000039
True
(0.27 secs, 85607928 bytes)
Prelude PrimeTest> primeQ 1000000000039
True
(1.38 secs, 457966212 bytes)


>           then f x (n+1) y
>           else False
>

A stylistic remark,

if condition then True else somethingMore

is often better expressed as

condition || somethingMore

or using guards, so you could write f as

f x n y = (n > y) || (x `rem` n /= 0 && f x (n+1) y)

or

f x n y
  | n > y          = True
  | x `rem` n == 0 = False
  | otherwise      = f x (n+1) y

>
>
>
>
> primeQ x = f x 2 y
>   where y = floor(sqrt(x))
>
>
>
> The compiler is very unhappy.  Apparently there's some ambiguity in
> this, and I'm kind of running around in circles.  I'd appreciate any
> help that will get me started.