Haskell Practice - Prime (2)

在寫了一個第一篇之後，scm 老師給予了很多建議

scm 提到...
Interesting code :). Some comments:

1. 如你所說 isPrime 是 map 加上 foldr (不過這個 isPrime 測的好像是「不是質數」？）。另外，makePrimeList 是 filter.
2. 其實 (&&) 這個 operator 碰到第一個參數是 False 的時候也並不會去算第二個。isPrime2 和 isPrime 的另一個不同點是碰到 y < sq 就停下來吧？這也可以用先做一個 takeWhile 達成。
3. 用 makeList 的版本為什麼比較慢不能馬上斷定，一個猜測是和 x ++ [c] 有關係。串列的 (++) 花的時間和第一個參數的長度成正比，所以每產生一個新的 c 都得從最開頭把這個串列旅行一遍。
   另外，由於 makeList 是 tail recursive 的，makePrimeList 必須等到整個 6n+1 6n+5 的串列產生完畢後才能動作。（比較之下 makePrimeList_2 則可以隨到隨做，[2..x] 這個 list 的元素生出來、測試過後，就丟掉了，並不佔空間。）不知道 makeList 會不會使得 heap 使用量變大，GC 變多，程式就慢了。你可寫一個不是 tail recursive 的 makeList 試試看嗎？

所以第一個問題 isPrime 是錯的，因為我一開始是寫 notPrime XD，但是問題算小，我馬上重寫了一下(順帶一提， scm 老師說的 && 特性，我不確定 Haskell 有，現在知道有了，記得這有一個名詞稱呼這種特性，但是忘了是什麼，在寫 C/C++ 時很常用，大部分是用在 pointer check is not null 上。)

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

isPrime :: Integer -> [Integer] -> Bool
isPrime x y
    | x == 2 = True
    | otherwise =
         case y of 
             [] -> True
             y:ys -> (x `mod` y /= 0) && isPrime x ys

這樣子應該就沒有錯了...(汗)，然後我們再很快速的寫成 map 格式，也連帶的使用到 lambda function ，因為我不知道怎麼樣寫的比較精簡了 XD

isPrime4 :: Integer -> [Integer] -> Bool
isPrime4 x y
    | x == 2 || y == [] = True
    | otherwise = and (map ( \e -> x `mod` e /= 0) y)
--     | otherwise = and (map (/=0) (map (x `mod`) y)) 

接著我再把稍微改版的程式試著用 takeWhile 改寫(takeWhile 的相對是 dropWhile)

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

isPrime5' :: Integer -> [Integer] -> Bool
isPrime5' x y =
     case y of
         [] -> True
         y:ys -> (x `mod` y /= 0) && isPrime5' x ys

最後一個問題就是 makeList，我就沒有寫了，我把 makePrimeList 寫成如下型式

makePrimeList4 :: Integer -> [Integer]
makePrimeList4 x = [2, 3] ++ makePrimeList4' 5 x False [] 

makePrimeList4' :: Integer -> Integer -> Bool -> [Integer] -> [Integer]
makePrimeList4' c e b x
    = if c < e then
          if isPrime5 c x then
              makePrimeList4' (c+add) e (not b) (x ++ [c])
          else 
              makePrimeList4' (c+add) e (not b) x
      else x
      where add = if b then 4 else 2

這樣子的 code 就不需要另外產生 list ，因為產生的當下就檢查，不要就丟掉了，然而在生成 prime list 的時候還是 tail recursive ，有嘗試過另外的方法，卻發現快不起來。

如果要將 (x ++ [c]) 變成 ([c] ++ x)，我嘗試寫了另外一個 isPrime7

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

這樣子的確可以完全避免掉 tail recursive 的問題，但是速度會比較慢，因為產生的數列是 11 7 5 3 2 這樣子的排序，一般檢查是否為質數是正向檢查，逆向的時候能夠在檢查次數上佔到的便宜其實不多 (如果該數是被 5 整除的話...)，所以這樣子寫反而比較慢，目前的想法是，如果想要完全漂亮的解決 tail recursive 問題的話，勢必是得重新設計方法而且更了解這個語言的。

---
可見自己數學真的不好 ... Orz