如何在Haskell中编写递归素数检查器？

Question

我对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

返回False.该else部件永远不会被评估,因此该函数从不调用自身.

我不确定为什么会这样.此外,这是否接近Haskell程序员如何处理这个问题？(我并不是说检查素性,我知道这不是这样做的方式.我只是这样做是为了练习).

Answer 1

问题出在这一行

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.

Answer 2

你的错误是一个简单的错字; 在结束时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而不是alllowercase.只是格式化,但这是习惯.

除了我可能会让事情更糟糕.在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,因此你不会意外地给它错误的值.