Haskell 素数测试

Question

我是 Haskell 的新手，我正在尝试一下:

isPrime :: Integer->Bool
isPrime x = ([] == [y | y<-[2..floor (sqrt x)], mod x y == 0])

我有几个问题。

为什么当我尝试加载 .hs 时，WinHugs 说:(Floating Integer, RealFrac Integer) 的实例isPrime 的定义所必需的?

当解释器在正确的集合中找到一个元素时，它会立即停止还是计算所有集合？我想你知道我的意思。

对不起我的英语。

Answer 1

1) 问题是 sqrt类型为 (Floating a) => a -> a ，但您尝试使用整数作为参数。因此，您必须先将 Integer 转换为 Floating，例如通过写 sqrt (fromIntegral x)
2) 我看不出为什么 == 不应该是懒惰的，但是为了测试一个空集合，你可以使用 null函数(这绝对是惰性的，因为它适用于无限列表):

isPrime :: Integer->Bool
isPrime x = null [y | y<-[2..floor (sqrt (fromIntegral x))], x `mod` y == 0]

但为了获得更惯用的解决方案，请将问题分解为更小的子问题。首先，我们需要 y*y <= x 的所有元素 y 的列表:

takeWhile (\y ->  y*y <= x) [2..]

那么我们只需要除 x 的元素:

filter (\y ->  x `mod`y == 0) (takeWhile (\y ->  y*y <= x) [2..])

然后我们需要检查该列表是否为空:

isPrime x = null (filter (\y ->  x `mod`y == 0) (takeWhile (\y ->  y*y <= x) [2..]))

如果这看起来对你来说很笨拙，请用 $ 替换一些括号

isPrime x = null $ filter (\y ->  x `mod` y == 0) $ takeWhile (\y ->  y*y <= x) [2..]

为了更加清楚，您可以“外包” lambda:

isPrime x = null $ filter divisible $ takeWhile notTooBig [2..] where
     divisible y = x `mod`y == 0
     notTooBig y = y*y <= x

您可以通过用 not $ any 替换 null $ filter 使其几乎“人类可读”:

isPrime x = not $ any divisible $ takeWhile notTooBig [2..] where
     divisible y = x `mod`y == 0
     notTooBig y = y*y <= x