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