I'm new to Haskell, and I'm trying a bit:
isPrime :: Integer->Bool
isPrime x = ([] == [y | y<-[2..floor (sqrt x)], mod x y == 0])
I have a few questions.
(Floating Integer, RealFrac Integer)
required for definition of isPrime
?Sorry about my english.
1) The problem is that sqrt
has the type (Floating a) => a -> a
, but you try to use an Integer as argument. So you have to convert your Integer first to a Floating, e.g. by writing sqrt (fromIntegral x)
2) I see no reason why == shouldn't be lazy, but for testing for an empty collection you can use the null
function (which is definitely lazy, as it works on infinite lists):
isPrime :: Integer->Bool
isPrime x = null [y | y<-[2..floor (sqrt (fromIntegral x))], x `mod` y == 0]
But in order to get an more idiomatic solution, break the problem into smaller sub-problems. First, we need a list of all elements y with y*y <= x:
takeWhile (\y -> y*y <= x) [2..]
Then we need only the elements that divide x:
filter (\y -> x `mod`y == 0) (takeWhile (\y -> y*y <= x) [2..])
Then we need to check if that list is empty:
isPrime x = null (filter (\y -> x `mod`y == 0) (takeWhile (\y -> y*y <= x) [2..]))
And if this looks to lispy to you, replace some of the parens with $
isPrime x = null $ filter (\y -> x `mod` y == 0) $ takeWhile (\y -> y*y <= x) [2..]
For additional clarity you can "outsource" the lambdas:
isPrime x = null $ filter divisible $ takeWhile notTooBig [2..] where
divisible y = x `mod`y == 0
notTooBig y = y*y <= x
You can make it almost "human readable" by replacing null $ filter with not $ any:
isPrime x = not $ any divisible $ takeWhile notTooBig [2..] where
divisible y = x `mod`y == 0
notTooBig y = y*y <= x