0 
isPrime :: Int -> Bool
isPrime n = leastDivisor n == n

leastDivisor :: Int -> Int 
leastDivisor n = leastDivisorFrom 2 n

leastDivisorFrom :: Int -> Int -> Int
leastDivisorFrom k n | n `mod` k == 0 = k
                     | otherwise      = leastDivisorFrom (k + 1) n

我的问题是：

  • 这个功能有什么设计问题？
4

1 回答 1

2

操作性太强了。它可以等价地表示为(*)

isPrime :: Integer -> Bool
isPrime n  =  [n] == take 1 [i | i <- [2..n], mod n i == 0]

所以它在视觉上更明显，更清晰，单线更容易处理。

尝试作为

GHCi> zipWith (-) =<< tail $ filter isPrime [2..]
[1,2,2,4,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,6,6,2,10,2,4,2,12,12,
4,2,4,6,2,10,6,6,6,2,6,4,2,10,14,4,2,4,14,6,10,2,4,6,8,6,6,4,6,8,4,8,10,2,10,2,6,4,6,8,4,2,4,12,8,4,
8,4,6,12,2,18,6,10,6,6,2,6,10,6,6,2,6,6,4,2,12,10,2,4,6,6,2,12,4,6,8,10,8,10,8,6,6,4,8,6,4,8,4,14,10
......

显示它有多慢。我们可以尝试将其重写为

isPrime n  =  null [i | i <- [2..n-1], mod n i == 0]
           =  none (\ i -> mod n i==0) [2..n-1]
           =  all (\ i -> mod n i > 0) [2..n-1]
           =  and  [mod n i > 0 | i <- [2..n-1]]

但[2..n-1]并不比短很多[2..n]，不是吗。它应该短得多，结束得早得多；甚至更短，里面有很多洞......

isPrime n = and [mod n p > 0 | p <- takeWhile (\p -> p^2 <= n) primes]
primes = 2 : filter isPrime [3..]

之后的下一个改进是完全摆脱mod。

leastDivisor n == n(*) 这表示与您正在执行的计算操作完全相同。take 1仅将数字的第一个除数作为列表；它的长度必然是1；将它与单元素列表[n]进行比较相当于将第一个（即最小的）除数与数字进行比较n。正是您的代码在做什么。

但在这种形式下，它（可以说）是一个更清晰的代码，更直观。至少对我来说是这样。:)

于 2019-12-22T19:46:22.420 回答