Haskell Practice - Ugly Numbers

題目就在這，我就不再多做說明了，這題寫完，暫時要停下來，把 scm 老師的信消化，然後鳥書繼續前進 XD。

is_un n
    | n == 1 = True
    | n `mod` 2 == 0 = is_un (truncate (fromIntegral n/fromIntegral 2))
    | n `mod` 3 == 0 = is_un (truncate (fromIntegral n/fromIntegral 3))
    | n `mod` 5 == 0 = is_un (truncate (fromIntegral n/fromIntegral 5))
    | otherwise = False


is_un2 n
    | n == 1 = True
    | n `mod` 2 == 0 = is_un2 (until (\x -> x `mod` 2 /= 0) (\x -> truncate (fromIntegral x/ fromIntegral 2)) n) 
    | n `mod` 3 == 0 = is_un2 (until (\x -> x `mod` 3 /= 0) (\x -> truncate (fromIntegral x/ fromIntegral 3)) n)
    | n `mod` 5 == 0 = is_un2 (until (\x -> x `mod` 5 /= 0) (\x -> truncate (fromIntegral x/ fromIntegral 5)) n)
    | otherwise = False

is_un3 n = foldl judge n [2,3,5] == 1
    where judge n y = until (\x -> x `mod` y /= 0) (\x -> truncate (fromIntegral x/ fromIntegral y)) n

un_list :: [Integer] -> Integer -> [Integer]
un_list (x:xs) n 
    | n == 0 = (x:xs)
    | otherwise = un_list (min:x:xs) (n-1) 
    where min = minimum (filter (>x) [u*v | u<-(x:xs), v<-[2, 3, 5]])

傳說中這題是一行就可以寫完的，但是我不知道怎麼寫，我還是一樣照我的想法寫 XD，剛開始的想法非常簡單，一直除 2, 3, 5，最後的結果不等於 1 就不是，這方法當然很慢，不過練習還是有用的，因為從 is_un 至 is_un3 可以讓我練一下 foldl ，也讓我明確的了解到 foldl 和 foldr 的根本性不同 (沒錯，我之前又完全搞錯了，剩下只有 fold fusion 要搞懂了)

最後一個 un_list 的想法則是比較正面，找到前面 list 乘於 2, 3, 5 然後大於 list 最大的數的數列最小值，這速度顯然快很多 XD。在這樣子的狀況下寫成 tail recursive 比較直覺，但是其實將整個數列反過來算也是 ok 的，所以我就索性反過來算了。測試結果如下 ...

*Main> reverse (un_list [5, 4, 3, 2, 1] 1495)
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,75,80,81,90,96,100,108,120,125,128,135,144,150,160,162,180,192,200,216,225,240,243,250,256,270,288, ...

同場加映 Python 版，不過真的只能說 Haskell 影響 Python 很深，在 list 操作部分很像，但是沒有 Haskell 來的漂亮 XD

def ugly_number(list_size):
    ug_list = [1]
    for i in range(0, list_size-1):
        ug_list.append(min(filter(lambda x: x>ug_list[len(ug_list)-1], [x*y for x in ug_list for y in [2,3,5]])))
    return ug_list

---
該繼續打底了 ... XD

---

2010/03/15 05:58 pm 今天晚上可能無法再做練習了，可能要先看一下 paper ，不過初步的破爛想法是

makePrime x = if prime (x+add) then (x+add)
            else makePrime (x+add) 
            where add = if x `mod` 6 == 1 then 4 else 2
primes = 5: map primeCircule2 primes

其實不是沒有想過一次生二個 element (試著寫 let p = 5:7: map (6+) p)，但是回傳時一定要產生一個 element，如果不是的時候總不能丟 0 XD，所以只好先交出一個破爛方法，剩下的明天再試。

---

2010/03/18 11:06 am 後來想到兩個數列分開算再用 merge 即可，不過速度上應該是佔不到便宜就是了 ...

makePrime_plusn n x = if prime (x+n) then (x+n) else makePrime_plusn n (x+6) 
primes = 5: map makePrime primes
primes2 = merge primes_plus2 primes_plus4 
    where primes_plus2 = 5: map (makePrime_plusn 6) primes_plus2 
          primes_plus4 = 7: map (makePrime_plusn 6) primes_plus4

Haskell Practice - Merge Sort

老實說我也不太清楚是不是 Merge Sort ，只是照著感覺寫，而且感覺是效率不佳的 Merge Sort ... Orz，其中的 merge 是 scm 老師寫的，他寫了一封信，我很認真的看再很認真的忘掉再重寫中。

insertionSort [] = []
insertionSort (x:xs) = merge [x] (insertionSort xs)

merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) 
    | x <= y = x : merge xs (y:ys)
    | otherwise = y : merge (x:xs) ys

測試結果如下:

*Main> mergeSort [3,1,5,2,6, -1, 10]
[-1,1,2,3,5,6,10]

---
想要改寫，不過應該是晚上的事了。

---

事情比想像中更糟，自己推一次，發現根本不是 Merge Sort 啊 ... Orz

---

上面那個應該是 insertion sort ... 緊急之間寫了下面這個 code 出來，但是會出錯 ... meeting 在即，等回來再說了 ...

mergeSort [] = []
mergeSort x = 
    if length x > 1 then 
        merge (mergeSort (fst (splitAt half x))) (mergeSort (snd (splitAt half x)))
    else x
    where half = truncate ( (fromIntegral (length x))/ (fromIntegral 2))

---

看起來是沒有出錯了，接下來該開始思考怎麼寫會比較好一點 XD。

---

2010/03/12 00:09 結果根本就在惡補怎麼操作 list ，發現自己是有看了，但是都忘完了 ... 到目前為止的版本

mergeSort (x:xs) 
    | xs == [] = [x]
    | otherwise = merge (mergeSort (take half (x:xs))) (mergeSort (drop half (x:xs)))
    where half = truncate ( (fromIntegral (length (x:xs)))/ (fromIntegral 2))

---

2009/03/12 10:19 AM 只是嘗試將 length 帶入 argument 中，實質上並無太大改變，我一直在想著長度的問題 ... 可是腦袋又是空掉了 ...

mergeSort [] = []
mergeSort x = mergeSort' x (length x) 

mergeSort' x l
    | l == 1 = x
    | otherwise = merge (mergeSort' (take half x) half) (mergeSort' (drop half x) (l-half))
    where half = truncate ((fromIntegral l)/(fromIntegral 2))

---

2009/03/14 11:38 pm 依 scm 在 comments 裡的建議把 uninterleave 寫出來，自己重寫 interleave ，發現有一點不太一樣(還好功能一樣 XD)

interleave [] ys = ys
interleave xs [] = xs
interleave (x:xs) (y:ys) = x:y:(interleave xs ys)
-- interleave (x:xs) (y:ys) = x:(interleave (y:ys) xs)

uninterleave :: [a] -> ([a],[a])
uninterleave [] = ([], [])
uninterleave (x:xs) = uninterleave' (x:xs) [] [] 

uninterleave':: [a] -> [a] -> [a] -> ([a], [a])
uninterleave' [] ys zs = (zs, ys)
uninterleave' (x:xs) ys zs = uninterleave' xs zs (x:ys)

mergeSort2 :: (Ord t) => [t] -> [t]
mergeSort2 [] = []
mergeSort2 (x:[])  = [x]
mergeSort2 xs = merge (mergeSort2 (fst (uninterleave xs))) (mergeSort2 (snd(uninterleave xs)))

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

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。

愛的 ... ?

某天我把 Clara 說給我的話說給 gb014388 聽之後，他在白板上是這樣子寫的

Clara: 愛的抱抱相反是冷漠。

---
XD