8

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

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

我有几个问题。

  1. 为什么当我尝试加载 .hs 时，WinHugs 会说：(Floating Integer, RealFrac Integer)定义所需的实例isPrime？
  2. 当解释器在正确的集合中找到一个元素时，它会立即停止还是计算所有集合？我想你知道我的意思。

对不起我的英语。

4

5 回答 5

17

1) 问题在于它sqrt具有 type (Floating a) => a -> a，但您尝试使用 Integer 作为参数。因此，您必须首先将 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
于 2010-12-27T20:15:34.210 回答
7

  1. 因为sqrt有类型Floating a => a -> a。这意味着输入必须是一种Floating类型，而输出必须是相同的类型。换句话说x，需要是一种Floating类型。但是，您声明x为 type Integer，这不是Floating类型。另外floor需要一个RealFrac类型，所以x也需要那个类型。

    错误消息建议您通过创建Integer一个Floating类型（通过定义一个实例Floating Integer（对于RealFrac.

    当然，在这种情况下，这不是正确的方法。相反，您应该使用fromIntegralto 转换x为 a Real（这是Floatingand的一个实例RealFrac），然后将其提供给sqrt.

  2. 是的。一旦==看到右操作数至少有一个元素，它就知道它不等于[]并因此返回False。

    话虽这么说，null检查列表是否为空是一种比[] ==.

于 2010-12-27T20:12:01.427 回答
1

关于第二点，它停止了，例如：

[] == [x | x <- [1..]]

退货False

于 2010-12-27T20:12:14.367 回答
1

Landei 的解决方案很棒，但是，如果您想要更高效的¹实施，我们有（感谢 BMeph）：

-- list of all primes
primes :: [Integer]
primes = sieve (2 : 3 : possible [1..]) where
     sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
     possible (x:xs) = 6*x-1 : 6*x+1 : possible xs

isPrime :: Integer -> Bool
isPrime n = shortCircuit || (not $ any divisible $ takeWhile inRangeOf primes) where
    shortCircuit = elem n [2,3] || (n < 25 && ((n-1) `mod` 6 == 0 || (n+1) `mod` 6 == 0))
    divisible y = n `mod` y == 0
    inRangeOf y = y * y <= n

“效率”来自于使用常数素数。它通过两种方式改进搜索：

  1. Haskell 运行时可以缓存结果，因此不会评估后续调用
  2. 它通过逻辑注释消除了一系列数字，该sieve值只是一个递归表，其中说列表的头部是素数，并将其添加到其中。对于其余的列表，如果列表中已经没有其他值构成数字，那么它 的素possible数也是所有可能素数的列表，因为所有可能的素数都采用 6*k-1 或 6*k-1 的形式除了 2 和 3 相同的规则也适用于shortCircuit快速退出计算

DF
的脚注 ¹ 它仍然是一种非常低效的寻找素数的方法。如果您需要大于几千的素数，请不要使用试除法，而是使用筛子。hackage有几个更 有效的实现。

于 2010-12-31T22:09:20.440 回答
-2
  1. 我认为 WinHugs 需要为 Integer 等导入一个模块...尝试 Int
  2. 解释器不会计算任何东西，直到你调用 egisPrime 32然后它会懒惰地计算表达式。

PS你的isPrime实现不是最好的实现！

于 2010-12-27T20:12:36.933 回答