Haskell Pratice - Prime

今日目標算是達成了，明天再繼續。原始想法很簡單，如何寫出一個 prime list ? 於是我就寫了第一版

prime :: Integer -> Bool
prime x 
    | x == 2 = True
    | otherwise = 
            isPrime [2..sq] x
            where sq = truncate (sqrt (fromIntegral x)) + 1

isPrime :: [Integer] -> Integer -> Bool
isPrime x y =
    case x of 
        [] -> False
        x:xs -> (y `mod` x == 0) || isPrime xs

makePrimeList :: [Integer] -> [Integer]
makePrimeList x =
    case x of
        [] -> [] 
        x:xs -> if prime x then  
                    [x] ++ makePrimeList xs
                else 
                    makePrimeList xs

其中的 where sq = truncate (sqrt (fromIntegral x)) + 1 是在 Josh Ko 的幫助下寫出來的，但是我得隔日再戰，我很明確的知道是轉型問題，但是並不是能夠完全說清楚為什麼要這樣做(他有說明，但是我得再看一下書)。

而且在這一版中的 isPrime 實在是太暴力了，其實可以用 map + and (or fold) 寫出來，並不一定要用 recursive 寫，所以我採用了另外一個寫法，即是檢查到 `mod` == 0 就停下來。

isPrime_2 :: Integer -> [Integer] -> Bool
isPrime_2 x y
    | x == 2 = True
    | otherwise =
        case y of
            [] -> True
            y:ys -> if y < sq then
                        if (x `mod` y == 0) then False
                        else isPrime_2 x ys
                    else True 
                    where sq = truncate (sqrt (fromIntegral x)) + 1

速度是明顯快上不少，但這版對我而言只剩最後一個問題，就是每呼叫一次 sq 就要算一次，我目前唯一想到的解法是，把 sq 也當成引數，於是我就寫成

isPrime_3 :: Integer -> [Integer] -> Bool
isPrime_3 x y 
    | x == 2 = True
    | otherwise =
        isPrime_3' x y (truncate (sqrt (fromIntegral x)) + 1)

isPrime_3' :: Integer -> [Integer] -> Integer -> Bool
isPrime_3' x y sq =
    case y of
        [] -> True
        y:ys -> if y < sq then
                    if (x `mod` y == 0) then False
                    else isPrime_3' x ys sq
                else True

最後，再寫一個 makePrimeList 的 code 就搞定了

makePrimeList :: Integer -> [Integer]
makePrimeList x = makePrimeList_2 [2..x] []

makePrimeList_2 :: [Integer] -> [Integer] -> [Integer]
makePrimeList_2 u v =
    case u of 
        [] -> []
        x:xs -> if isPrime_3 x v then
                    [x] ++ makePrimeList_2 xs (v++[x])
                else
                    makePrimeList_2 xs v

最後 run 一下成果

*Main> makePrimeList 100
[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]

其實還可以更快，但是就明天再來來，依現在的程度寫出的 code ，雖然普通，可是很開心。

---
本週目標：練習 Prime

---

馬上就打了自己的嘴吧，我試著嘗試產生 6n+1 6n+5 的 list 用以減少 prime 的檢查次數，於是很粗糙的寫了如下的 code

makeList :: Integer -> Integer -> Bool -> [Integer] -> [Integer]
makeList e c b x =
    if c < e then
        if b then
            makeList e (c+4) False (x ++ [c])
        else
            makeList e (c+2) True (x ++ [c])
    else
        x

然後將 makePrimeList 改成如下

makePrimeList :: Integer -> [Integer]
makePrimeList x = makePrimeList_2 ([2, 3] ++ makeList x 5 False []) []

結果速度反而慢到嚇人啊...Orz 完全不知道為什麼，看來要好好研究了 XD。