Haskell素數函數不起作用

Question

我在過去的幾天裏開始學習Haskell，並且在這段代碼中遇到了麻煩。我試圖做一個函數，它會生成一個給定初始列表（至少包含2）的素數列表，最大列表長度，當前除數的索引（應該從1開始，將當前數字除以全部到目前爲止的素數）和當前要測試的數字（奇數）。

我知道這不是很優雅或高效，但是這個代碼不會編譯或運行，所以我想在優化之前先修復它。雖然對此的建議也會很酷。

primes = [2,3,5,7,11,13] 

genPrimes primes max curDiv curTest 
    | length primes >= max = primes 
    | primes !! curDiv > floor . sqrt curTest = genPrimes (primes ++ [curTest]) max 1 (curTest + 2) 
    | curTest `mod` primes !! curDiv == 0 = genPrimes primes max 1 (curTest + 2) 
    | curTest `mod` primes !! curDiv /= 0 = genPrimes primes max (curDiv + 1) curTest 

我收到以下錯誤，當我嘗試編譯上面的代碼：

Couldn't match expected type `a0 -> c0' with actual type `Integer' 
Expected type: [a0 -> c0] 
    Actual type: [Integer] 
In the first argument of `genPrimes', namely `primes' 
In the expression: genPrimes primes 50 1 15 

Answer 1

ja。已經給出了正確的答案，但是你的解決方案不是很習慣。下面是一個簡單的方法來生成素數的無限名單：

primes = 2 : filter isPrime [3,5..] 

isPrime n = all ((/=0).(n `mod`)) $ takeWhile (\p -> p*p <= n) primes 

primes很容易理解，這2定義爲總理，並檢查所有下面的奇數，如果他們是素數。 isPrime稍微複雜一些：首先我們取所有的素數小於或等於n的平方根。然後我們檢查我們是否將n除以我們沒有提醒的所有這些素數等於0. isPrime指的是primes，但這不是問題，因爲Haskell是懶惰的，我們從不需要「太多」素數來進行檢查。

列表primes是無限的，但你可以寫一些像take 10 primes。

注意，該代碼有其自身的問題，請參見http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Answer 2

你已經得到了論據「：」逆轉：標量轉到左邊，或者您也可以做一個單獨的列表並連接：

| primes !! curDiv > floor . sqrt curTest = genPrimes (primes++[curTest]) max 1 curTest + 2 

Answer 3

至少，你的代碼應該是

primes = [2,3,5,7,11,13] 

genPrimes primes max = go primes (length primes) 1 (last primes + 2) 
where 
    go prs len d t 
    | len >= max    = prs 
    | (prs !! d) > (floor . sqrt . fromIntegral) t 
           = go (prs++[t]) (len+1) 1 (t + 2) 
    | t `rem` (prs !! d) == 0 = go prs  len 1 (t + 2) 
    | t `rem` (prs !! d) /= 0 = go prs  len (d + 1) t 

test n = print $ genPrimes primes n 
main = test 20 

然後你重新組織這樣（抽象出每個候選號碼進行的測試，作爲noDivs功能）：

genPrimes primes max = go primes (length primes) (last primes + 2) 
where 
    go prs len t 
    | len >= max  = prs 
    | noDivs (floor . sqrt . fromIntegral $ t) t prs 
        = go (prs++[t]) (len+1) (t + 2) 
    | otherwise  = go prs  len (t + 2) 

noDivs lim t (p:rs) 
    | p > lim   = True 
    | t `rem` p == 0 = False 
    | otherwise  = noDivs lim t rs 

那麼你重寫noDivs爲

noDivs lim t = foldr (\p r -> p > lim || rem t p /= 0 && r) False 

然後你注意到go只是通過這樣的篩選數字，通過noDivs測試：

genPrimes primes max = take max (primes ++ filter theTest [t, t+2..]) 
where 
    t = last primes + 2 
    theTest t = noDivs (floor . sqrt . fromIntegral $ t) t 

但這並沒有工作，因爲theTest需要通過primes（全新的素數，因爲他們正在找到）到noDivs，但我們正在建設這個whole_primes列表（因爲take max (primes ++ ...)），所以有一個惡性循環？不，因爲我們只測試一個數字的平方根：

genPrimes primes max = take max wholePrimes 
where 
    wholePrimes = primes ++ filter theTest [t, t+2..] 
    t   = last primes + 2 
    theTest t = noDivs (floor . sqrt . fromIntegral $ t) t wholePrimes 

這是現在的工作。但最後，沒有什麼特殊的genPrimes現在，它只是take美化了電話，和初始primes名單實際上可以縮小，所以我們得到（改變參數安排noDivs一點，使其界面更加通用）：

primes = 2 : 3 : filter (noDivs $ tail primes) [5, 7..] 

noDivs factors t = -- return True if the supplied list of factors is too short 
    let lim = (floor . sqrt . fromIntegral $ t) 
    in foldr (\p r-> p > lim || rem t p /= 0 && r) True factors 
    -- all ((/=0).rem t) $ takeWhile (<= lim) factors 
    -- all ((/=0).rem t) $ takeWhile ((<= t).(^2)) factors 
    -- and [rem t f /= 0 | f <- takeWhile ((<= t).(^2)) factors] 

全局primes列表現在被無限期地定義（即「無限」）。 Next step是要認識到，在質數的連續平方之間，要測試的因子列表的長度將是相同的，對於每個新的分段遞增1。我們可以直接生成它們的倍數（因此每一個都是從它的主要因素中生成的），而不是測試每個數字是否是它是是其平方根以下任何一個素因子的倍數。