Naive primality test and summation

Question

I am starting to learn Haskell, so I coded a naive solution to the primality test and summation of primes (Project Euler Problem 10: sum of all primes under 2 million) . As I have an imperative programming background, can you tell me if my code is functional enough?

isqrt :: Int -> Int 
isqrt n = floor(sqrt(fromIntegral n))
factors n = filter (\i -> n `mod` i == 0) [1..(isqrt(n))]
is_prime n = (factors n) == [1]
main = print (sum (filter is_prime [2..2000000]))

• SylvainD: Not an haskell expert (to say the least) but when you know you will perform a high number of prime checks and you know an upper bound for the number you'll check, it is much more efficient to implement some kind of Sieve of Eratosthenes.
• Caridorc: I know but I just wanted ro implement a very easy algoritmh

Answer 1

You have some of the right idea, but it looks like you're writing in Lisp. ;-)

There's no need to surround a single parameter in parentheses to pass it to a function, you mostly get this right so I think this one instance was just a slip up.

factors n = filter (\i -> n `mod` i == 0) [1..(isqrt(n))]
-- ^ ^

Function application has the highest precedence of any operator in Haskell, so these parentheses are unnecessary.

factors n = filter (\i -> n `mod` i == 0) [1..(isqrt n)]
-- ^ ^
is_prime n = (factors n) == [1]
-- ^ ^

Common Haskell style often prefers function composition to function application.

isqrt n = floor . sqrt . fromIntegral $ n

Are you familiar with function composition from mathematics? It's the same thing here, f . g $ x is equivalent to f (g x), but it puts the emphasis of the code on the composition of functions and not the manipulation of values. This is a different mindset from what you're going to be used to coming from an imperative language, but it is integral to developing the Haskell "house style" and really effectively leveraging combinators and function composition.

Haskellers also love writing functions pointfree. This means leaving off the arguments that are being passed to your function where possible. Check out the Haskell Wiki on pointfree style for some motivation and examples.

isqrt = floor . sqrt . fromIntegral

All top-level definitions should be annotated with a type signature in Haskell. There are myriad reasons for always doing this, including acting as documentation, providing necessary information to the compiler on occasions, serving as a check against your own understanding of what your function is doing, &c.

factors :: Int -> [Int]
is_prime :: Int -> Bool
main :: IO ()

Common Haskell style is to use camelCase instead of snake_case, so isPrime instead of is_prime.

Wherever possible, Haskellers usually prefer case analysis to equality testing. If you rewrite factors to exclude testing 1 (which is a tautological case anyway, why bother evaluating it?) you can check if the list returned by factors is null with null, which enables more function composition goodness.

factors :: Int -> [Int]
factors n = filter (\i -> n `mod` i == 0) [2..isqrt n]
isPrime :: Int -> Bool
isPrime = null . factors

---

Here's the whole thing with my style adjustments.

isqrt :: Int -> Int 
isqrt = floor . sqrt . fromIntegral
factors :: Int -> [Int]
factors n = filter (\i -> n `mod` i == 0) [2..isqrt n]
isPrime :: Int -> Bool
isPrime = null . factors
main :: IO ()
main = print . sum . filter isPrime $ [2..2000000]

Line breaks are important too. Doesn't it look much less cramped?

---

A comprehensively correct version of isPrime using guards to defend the honor of the negative numbers.

isPrime :: Int -> Bool
isPrime n | n < 2 = False
 | otherwise = null . factors $ n