将 isPrime() Python 转换为 Haskell
Converting isPrime() Python to Haskell
我有一个工作(尽管效率低下)函数来检查 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
最简单的列表理解:
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
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
可以帮到你。
尝试将其转换为尾递归,而不是使用循环。
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:])
我有一个工作(尽管效率低下)函数来检查 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
最简单的列表理解:
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
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
)。你怎么能解决你原来的问题?在您的情况下,将 anyTrue
值作为元素很重要。幸好有个函数any
可以帮到你。
尝试将其转换为尾递归,而不是使用循环。
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:])