1

我对 Haskell（以及一般的函数式编程）非常陌生，我正在尝试一些基本练习来尝试理解该语言。我正在编写一个“朴素”的素数检查器，它将输入下的每个数字除以检查是否有余数。到目前为止，我学到的唯一结构是理解列表和递归函数，所以我仅限于此。这是我正在尝试的：

isprime 1 = False
isprime 2 = True
isprime n = isprimerec n (n-1)

isprimerec _ 1 = False
isprimerec n t = if (n `rem` t) == 0 then False else isprimerec n (n-1)

目的是用户将使用isprime n. 然后isprime将用于isprimerec确定该数字是否为素数。这是一种非常迂回的方式，但由于我对 Haskell 的了解有限，我不知道任何其他方式。

当我尝试这个时会发生以下情况：

isprimerec 10 9

永远运行。我必须使用 Ctrl+C 来阻止它。

isprimerec 10 5

返回假。该else部分永远不会被评估，因此该函数永远不会调用自己。

我不确定为什么会这样。此外，这是否接近于 Haskell 程序员解决这个问题的方式？（我不是说检查素数，我知道这不是这样做的方法。我只是作为练习这样做）。

4

4 回答 4

6

您的错误是一个简单的错字；最后isprimerec，您的第二个参数变为n-1而不是t-1. 但除此之外，该功能不是很地道。这是我如何编写它的第一遍：

isPrime :: (Ord a, Integral a) => a -> Bool
isPrime n | abs n <= 1 = False
isPrime 2 = True
isPrime n = go $ abs n - 1
  where go 1 = False
        go t = (n `rem` t /= 0) && go (t-1)

（我可能会调用类似的go东西checkDivisors，但是go对于循环来说是惯用的。）请注意，这会暴露代码中的错误：一旦go是本地的isPrime，您不需要传递n，因此更清楚的是递归它是不正确的. 我所做的更改按重要性的粗略顺序排列：

  1. 我做isprimerec了一个本地函数。没有其他人需要调用它，并且我们丢失了额外的参数。

  2. 我把这个功能全部完成了。没有理由失败0，也没有任何理由因为负数失败。（从技术上讲，p是素数当且仅当 - p是素数。）

  3. 我添加了一个类型签名。养成一个好习惯。使用Integer -> Bool, 甚至Int -> Bool, 也是合理的。

  4. 我切换到 interCaps 而不是全小写。只是格式化，但这是习惯性的。

除了我可能会让事情变得更简洁。在 Haskell 中手动递归通常是不必要的，如果我们完全摆脱它，你的 bug 就变得不可能了。您的函数检查从2到的所有数字n-1不除n，因此我们可以直接表示：

isPrime :: (Ord a, Integral a) => a -> Bool
isPrime n | abs n <= 1 = False
          | otherwise  = all ((/= 0) . (n `rem`)) [2 .. abs n - 1]

你可以把它写在一行上

isPrime :: (Ord a, Integral a) => a -> Bool
isPrime n = abs n > 1 && all ((/= 0) . (n `rem`)) [2 .. abs n - 1]

但看到最后两种实现中的任何一种，我都不会感到惊讶。正如我所说，这些实现的好处是你的拼写错误不可能在这些表示中出现：t隐藏在 的定义中all，所以你不能不小心给它错误的值。

于 2013-02-04T19:04:00.740 回答
6

问题出在这一行

isprimerec n t = if (n `rem` t) == 0 then False else isprimerec n (n-1)

你(n - 1)在它应该在的地方使用作为第二个参数(t - 1)。还有一点，我想你想要这个isprimerec _ 1案子= True。

至于您关于这是否是惯用的更普遍的问题，我认为您走在正确的轨道上。 ghci有一个不错的命令行调试器。我通过将您的代码放在一个文件中，加载它，然后发出命令来发现这一点:break isprimerec。然后我调用了您的函数并使用:step.

于 2013-02-04T18:45:04.873 回答
3

您的else分支已损坏，因为它isprimerec n (n-1)每次都调用。你可能应该改写isprimerec n (t-1)让它倒计时。

您还可以使用高阶函数all来简化此操作。

isprime 1 = False
isprime n = all (\t -> n `rem` t /= 0) [2..(n-1)]
于 2013-02-04T18:43:53.543 回答
1

好吧，你有两个错误：你的

isprimerec _ 1 = False
isprimerec n t = if (n `rem` t) == 0 then False else isprimerec n (n-1)

本来应该

isprimerec _ 1 = True
isprimerec n t = if (n `rem` t) == 0 then False else isprimerec n (t-1)

或者，通过列表理解，

isprime n = n>1 && and [ rem n t /= 0 | t <- [n-1,n-2..2] ]

（内部化那个额外的参数t，无论如何它是一个技术性问题！--啊哈，但是那是什么and，你问？就像这个递归函数一样foldr (&&) True :: [Bool] -> Bool。）

但是现在一个主要的算法缺陷在视觉上变得很明显：我们以错误的顺序进行测试。如果我们按升序测试会更快：

isprime n = n>1 && and [ rem n t /= 0 | t <- [2..n-1] ]

sqrt如果我们停在,甚至更快

isprime n = n>1 && and [ rem n t /= 0 | t <- [2..q] ]
   where  q = floor (sqrt (fromIntegral n))

或仅在2之后通过2进行测试（如果我们已经通过2进行了测试，为什么要通过6进行测试？）：

isprime n = n>1 && and [ rem n t /= 0 | t <- 2:[3,5..q] ]
   where  q = floor (sqrt (fromIntegral n))

或仅按素数（如果我们已经通过3测试，为什么要按9测试？）：

isprime n = n>1 && and [ rem n t /= 0 | t <- takeWhile ((<= n).(^2)) primes ]
primes = 2 : filter isprime [3..]

为什么在过滤素数时测试偶数- 首先不生成它们不是更好吗？

primes = 2 : filter isprime [3,5..]

但isprime总是测试除以2——但我们只给它输入奇数；所以，

primes = 2 : 3 : filter (noDivs (drop 1 primes)) [5,7..]
noDivs factors n = and [ rem n t /= 0 | t <- takeWhile ((<= n).(^2)) factors ]

为什么要生成3的倍数（即[9,15 ..] == map (3*) [3,5..]），只是为了稍后测试和删除它们？--

{-       [5,7..]
    ==   [j+i | i<-[0,2..], j<-[5]]                 -- loop unrolling, 3x:
    ==   [j+i | i<-[0,6..], j<-[5,7,9]]
    == 5:[j+i | i<-[0,6..], j<-[7,9,11]]            
    == 5:[7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43, ...
    \\   [  9,      15,      21,      27,      33,      39,       ...
    ==   [j+i | i<-[0,6..], j<-[  9   ]]
-}
primes = 2:3:5: filter (noDivs (drop 2 primes)) 
         [j+i | i<-[0,6..], j<-[7,  11]]

我们也可以提前跳过5的倍数（作为欧拉筛的另一个步骤, ）：euler (x:xs) = x : euler (xs `minus` map (x*) (x:xs))

--       [j+i | i<-[0, 6..], j<-[7, 11]]            -- loop unrolling, 5x:
--  == 7:[j+i | i<-[0,30..], j<-[11,13,17,19,23,25,29,31,35,37]]
--  \\   [j+i | i<-[0,30..], j<-[               25,      35   ]]

primes = 2:3:5:7: filter (noDivs (drop 3 primes)) 
         [j+i | i<-[0,30..], j<-[11,13,17,19,23,   29,31,   37]]

......但这已经够远了，就目前而言。

于 2013-02-07T19:37:40.323 回答