在Haskell中生成素数的有限列表 [英] Generating finite lists of primes in Haskell

问题描述

在Haskell中有很多关于生成质数的主题，但是我认为它们都依赖于'isPrime'函数，如果我们还不知道素数序列，它应该看起来像这样:

There are a lot topics on generating prime numbers in Haskell, but in my opinion, they all rely on 'isPrime' function, which, if we don't know the primes sequence yet, should look like:

isPrime k = if k > 1 then null [ x | x <- [2,3..(div k 2) + 1], k `mod` x == 0]
                     else False

(div可能会替换为sqrt，但仍然...)

(div might be replaced with sqrt, but still...)

我尝试基于归纳定义"构造素数(假设我们有一组第一个 n 素数，然后是(n + 1)th 个素数是最小整数，因此第一个 n 质数都不是其除数).我试图以斐波那契数列的方式来做到这一点，即:

I've tried to construct prime numbers based on 'inductive definition' (assume we have a set of first n primes, then (n+1)th prime is the least integer such that none of the first n primes is a divisor of it). I've tried to do it in the Fibonacci sequence way, which is:

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fibs !! n
    where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

最后我得到了这个

-- checking if second number is a divisor of first one
ifDoesn'tDivide :: Int -> Int -> Bool
ifDoesn'tDivide n k 
    | mod n k == 0 = False
    | otherwise    = True

-- generating list which consists of first n prime numbers
firstPrimes :: Int -> [Int]
-- firstPrimes 1  = [2]
firstPrimes n     = take n primes 
    where primes = 2:(tail primes) ++ 
         [head [x | x <- [3,4..], k <- primes, ifDoesn'tDivide x k == True]]

但是它不起作用，当n >= 2时堆栈溢出.关于如何解决它的任何建议?

But it doesn't work, stack overflow when n >= 2. Any advice on how to fix it?

"Haskell可以根据自身定义数据结构，从而有效地创建了无限的数据结构"..前面提到的那些质数和Fibonacci序列是根据自身定义数据结构的特殊情况，Fibonacci序列工作得很好，但是这些primes不能.

"Haskell can define data structures in terms of themselves in effect creating infinite data structures". Those prime numbers and Fibonacci sequences mentioned earlier are specific cases of defining data structures in terms of themselves, and Fibonacci sequence works just fine, but these primes doesn't.

我错过了什么吗，这两种算法在本质上是否有所不同?

Am I missing something, are those two algorithms different in a substantive way?

P.S.所以，我想，我只是在寻找大多数"Haskellish"方式来做到这一点.

P.S. So, I think, I'm just looking for most 'Haskellish' way to do that.

推荐答案

您始终可以使用在Haskell中相当精美的筛子.

You can always use a sieve which is rather elegant in Haskell.

primes = sieve [2..]

sieve (p : xs) = p : sieve [ x | x <- xs, x `mod` p > 0 ]

所以要得到前10个素数

So to get the first 10 primes

> take 10 primes
[2,3,5,7,11,13,17,19,23,29]

请注意，虽然未明确使用isPrime，但列表理解功能可确保列表上的每个数字都必须相对于其前面的所有素数均为质数.

Notice that while isPrime is not explicitly used the list comprehension ensures that every number on the list must be prime relative to all the primes preceding it, which is to say prime.

这效率更高，它是 Eratosthenes筛子 (编辑).

This is more efficient and it's at the heart of Eratosthenes' sieve(Edit).

上面的代码是第一个示例:

The code above is the first example in:

• Melissa E. O'Neill，真正的Eratosthenes筛子

本文详细介绍了Haskell中筛子的有效实施以及惰性在计算中的作用.强烈推荐！

The paper goes in to much more detail about the efficient implementation of sieves in Haskell and the role of laziness in the computation. Highly recommended!

这篇关于在Haskell中生成素数的有限列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！