haskell中的素數程序

我正在查找一個Haskell中的程序，它測試給定的數字是否爲素數。haskell中的素數程序

prime :: (Integral a) => a -> Bool 
prime 1 = True 
prime x = and [ x `mod` y /= 0 | y <- [2..(x-1)] ]

我不明白這是什麼and的目的：prime x = and [。

來源

2014-04-17 unexim

雖然不是素數。 – karakfa

儘管這個問題已經回答了，請允許我補充幾件事情：當檢查的and源，您可以：

and :: [Bool] -> Bool 
and = foldr (&&) True

，以通知第一件事是，and採用布爾變量的列表，並返回單個布爾變量，並且所述表達x mod y /= 0計算結果爲True或False（因此擬合[BOOL]要求）。

更重要的是，foldr是一個懶惰的摺疊。所以這裏的懶惰摺疊是最佳的，因爲&&是一個半嚴格的運算符。因此，與半嚴格運算符組合的懶惰摺疊將在遇到第一次發生時產生短路評估。因此，在實際的情況下，非素數,and將避免評估整個列表，從而爲您節省時間。不要把我的話，如果你想定義的and自己嚴格的版本（使用更嚴格的foldl）：

andStrict :: [Bool] -> Bool 
andStrict x = foldl (&&) True 

primeStrict :: (Integral a) => a -> Bool 
primeStrict x = andStrict [x `mod` y /= 0 | y <- [2..(x-1)]]

現在運行：

prime 2000000000

注意如何那是快？現在做到這一點，但在它崩潰之前打斷它的內存堆棧：

primeStrict 2000000000

這顯然比較慢，您能夠中斷它。這是and的角色，這就是爲什麼and是使用foldr編寫的，因此爲什麼選擇它作爲您發佈的示例代碼。希望有助於作爲支持的答案。

來源

2014-04-17 20:41:52 eazar001

and對列表的所有元素執行邏輯和操作。

素數只能由一個人自己整除;這意味着一旦除數（無餘數）存在於2和2之間，這個數字就不是素數。

列表理解生成一個布爾值列表，其對應於您的x是否可以被上述範圍內的數字整除。

只要它們中的任何一個都是錯誤的（一個部分發生了零餘數），這個數字就不是素數。

考慮：

x = 7 
[7 % 2 /= 0 -> True, 7 % 3 /= -> True, ...] 
-- now applying and 
True && True && ... && True evaluates to True

and可被表示爲可對列表進行更一般的操作 - 使用邏輯和一個倍。如：and' = foldr (&&) True。

來源

2014-04-17 14:03:08 ScarletAmaranth

如果它執行邏輯和操作，它不應該是這樣的：'&&'？ – unexim

@unexim並帶有1個參數：布爾值列表; （&&）需要2個參數：兩個布爾值 – ScarletAmaranth

@unexim同樣，'和[a，b，c，d]'與'a && b && c && d'相同，因此'和'不能被命名爲'&&' 。 – Ingo

表達

[x `mod` y /= 0 | y <- [2..(x - 1)]

是Bool秒的列表，因爲mod x y /= 0（因爲反引號格式的前綴符號）返回一個Bool。該and功能只是做一個邏輯列表中的每個元素和，所以

and [True, False] == False 
and [True, True] == True

來源

2014-04-17 14:05:12 bheklilr

haskell中的素數程序

回答

相關問題