将 isPrime() Python 转换为 Haskell

Question

我有一个工作（尽管效率低下）函数来检查 Python 中的数字是否为素数，我想将其转换为 Haskell。现在效率对我来说并不重要，因为我主要专注于在 Haskell 中制作一个可读的算法，该算法使用初学者可以理解的语言特征。

我是 Haskell 的新手，所以我可能对如何处理这个问题有错误的想法。我的基本算法是检查一个数字是否为奇数且大于 2，如果是，则检查它是否可以被 2 之前的任何数字整除。

问题：我不知道如何设置 i 等于 [2..n] 范围内的递增项。

问题：有没有办法用一个变量遍历一个范围并引用它？

Python:

def is_prime(n):
    if n < 2: 
        return False # by definition, numbers smaller than 2 are not prime
    if n == 2: # edge case, 2 is the only even number that is prime
        return True
    if (n % 2) == 0:
        return False # if even, n is not prime (except 2)
    else:
        for i in range(2,n): #iterate from 2 to the input(n)-1 (since range() is non-inclusive of stop param)
            if (n % i == 0): #if n is divisible by a number that isn't 1 or itself...
                return False # ...it isn't prime
    return True

Haskell（我目前拥有的）：

isPrimeInner :: Int -> Bool
isPrimeInner n = map (n `rem` i == 0) [2..n] where i 
   -- I don't know how to set i equal to an increasing term 
   -- in the range [2..n]

isPrime :: Int -> Bool 
isPrime 2 = True -- edge case
isPrime n = if n < 2 
              then False 
            else if n `rem` 2 == 0 
              then False
            else isPrimeInner n

Answer 1

最简单的列表理解：

isPrime :: Int -> Bool
isPrime n = n > 1 && ( n == 2 ||
   null [ () | i <- [2..n-1], rem n i == 0] )
   --          ~~~~~~~~~~~~~

此处 i 是从范围 2 .. n-1 中提取的，即它采用从 2 到 n-1 的递增值，一次一个。

当它对 n 进行无余数整除时，会产生一个 () 值作为输出列表的成员，然后用 null 测试它是否为空。因此，该代码表达了这样的概念：“不存在这样的 i 从 2 到 n-1 平均划分 n”。 =29=]

i <- [2..n-1] 部分被称为列表理解的 生成器 部分，rem n i == 0 是 测试表达式 .

测试：

> filter isPrime [0..545]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,
137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,
271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,
431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541]
it :: [Int]

> length it
100

感谢 Haskell 的惰性求值，当给定复合参数 n 时，isPrime 会尽快失败，其中最小 n.

的除数 i

Answer 2

Haskell 中没有分配。不幸的是，您遇到了一个需要您学习新概念的主题：与其专注于单个值 (x)，不如专注于完整的 range/list 个值。

让我们假设 n = 8。 Python 程序员可能会迭代 (x in i in range(2, n))，Haskell 程序员可能会将输入列表 [2..n] 转换为结果列表并从那里继续解决问题：

xs = [   2,     3,    4,     5, ...]  -- input [2..n]
ys = [True, False, True, False, ...]  -- the resulting list of the divisibility test

因此我建议将问题分解并解决两个sub-problems:

如何从 xs 计算 ys？
假设您有整除测试列表 (ys)。你怎么能解决你原来的问题？在您的情况下，将 any True 值作为元素很重要。幸好有个函数any可以帮到你。

Answer 3

尝试将其转换为尾递归，而不是使用循环。

isPrimeHelper :: Integer -> [Integer] -> Bool
isPrimeHelper p (i:is) 
    | i*i > p = True
    | p `rem` i == 0 = False
    | otherwise = isPrimeHelper p is

isPrime :: Integer -> Bool
isPrime p = isPrimeHelper p [2..p]

isPrimeHelper是循环的递归版本，其中出现的i就像循环中的i一样，你可以跟踪它。

对于等效的 Python 代码：

def isPrimeHelper(p : int, xs : [int]):
  i = xs[0]
  if i*i >p:
    return True
  elif p % i == 0:
    return False
  else:
    return isPrimeHelper(p, xs[1:])

将 isPrime() Python 转换为 Haskell

Converting isPrime() Python to Haskell

python

haskell

primes

primality-test