[Note] A small difference between Haskell and Python in FP

我不得不說，寫關於數學的東西，Haskell 看起來真的漂亮的多。舉個例子來說說，我想要寫的 function 是

m = 8
rs_m = 0.9 
gramma = 6.27
d_st(a_st) = 1+m*a_st
d_dyn(a_dyn) = rs_m + (1-rs_m)*a_dyn
d(a_st, a_dyn) = d_st(a_st)/d_dyn(a_dyn)

用 Haskell 寫的話，其實跟上面很像 XD

d_st a_st = 1 + m*a_st
d_dyn a_dyn = rs_m + (1-rs_m)*a_dyn 
d a_st a_dyn = (d_st a_st)/(d_dyn a_dyn)

用 Python 寫的話，就會變成 ...

delta_st = lambda alpha_st: 1 + 8*alpha_st
delta_dyn = lambda alpha_dyn: rs_m + (1-rs_m)*alpha_dyn
delta = lambda alpha_st, alpha_dyn: delta_st(alpha_st)/ delta_dyn(alpha_dyn)

用 Python 最大的問題是 ... 看不太到參數，當然可以用 def delta(alpha_st, alpha_dyn): ... 寫，只是我好懶，其實也不是很大的差別(當然在其他的特性上會差很多)，不過就基本的寫法來說，我還是比較喜歡 Haskell 的。這或許也有可能是某個程度寫 Python 寫到累了想換新口味 XD? 就很單純的想法嘍 XD。

---
單純記錄 XDXD。

小試牛刀 - 算出檔案每一列的總和

今天處理程式的時候，遇到一個很簡單的檔案，長的如下

19 2 1 1 1
6 2 0 0 0
1 2 0 0 0
3 2 0 0 0
3 1 0 0 0
4 2 2 2 2
...

每一行代表一筆資料，然而，我想要得到每一列的總和。這其實是一個很簡單不過的題目，大一程式設計就可以寫的出來 XD。那麼有趣之處是什麼 XD? 如果我用 Python 來撰寫的話，要怎麼樣才可以寫的很有趣 ?

首先是讀檔，轉換資料成一個 list。我不打算浪費太多時間在寫這個方面，所以我是用暴力法撰寫。

f = open('filename.txt', 'r')
data = [[int(d) for d in l.split()] for l in f.readlines()]
f.close()

這樣子我們可以得到一個 list of list，每一個 element 的 type 皆為 integer，所以問題是，如何得到每一行的縱向總和 ? 直覺方式是雙層迴圈來搞定，這可能是最快也最直接想到的方法，不過我不想要，因為我覺得這實在是不美好 XD。就我的想法是，我當下想到的是 fold， fold list of list to a list. 稍微想了一下，就寫出了下面這行 code

sum_list = reduce(lambda x, y: [u+v for u, v in zip(x,y)], data)

其實用 Haskell 寫會更漂亮 ... 不過我還沒學 monad ... Orz (趕快學!!)

---
臨時筆記 XD

Haskell Learning Source

從 wiki 上移過來，大概會改變寫長文的寫作風格，拆成許多個小篇的來寫。

• Hayoo, Hoogle - function's type information (include hackageDB's package)
• hackageDB - package information, we can use cabal command install it.
• Haskell Cafe – Mailing List. You can google keyword, for example you can use google search like the following

  keyword site:http://www.haskell.org/pipermail/haskell-cafe/

---
持續寫作

Haskell Practice - Natural Number

其實就照著書上的教學盡量自己推然後寫，大概是看了 fold fusion ，直觀意義大概就是直接代入後可以少一層，然而這樣子做的好處在 function compose 上可能會少一些動作吧。這篇大概是做個紀錄。不過對我自己而言，做這個練習算是讓我體會到很多事，所有的事都可以依靠簡單的元素來完成時，真的是一件很漂亮的事 !!

data Nat = Zero | Succ Nat
    deriving(Show)

createNat :: Integer -> Nat
createNat i = createNat' i Zero

createNat' :: Integer -> Nat -> Nat
createNat' 0 n = n
createNat' i n = createNat' (i-1) (Succ n)

plusNat :: Nat -> Nat -> Nat
plusNat m Zero = m
plusNat m (Succ n) = Succ (m `plusNat` n)

multNat :: Nat -> Nat -> Nat
multNat m Zero = Zero
multNat Zero n = Zero
multNat (Succ m) (Succ n) = (multNat (Succ m) n) `plusNat` (Succ m)

divNat :: Nat -> Nat -> Nat
divNat (Succ m) Zero = undefined
divNat Zero _ = Zero
divNat (Succ m) (Succ n)
    | (Succ m) == (Succ n) = Succ Zero
    | (Succ m) < (Succ n) = Zero
    | (Succ m) > (Succ n) = (Succ Zero) `plusNat` (divNat ((Succ m) `subNat` (Succ n)) (Succ n))

exponNat :: Nat -> Nat -> Nat
exponNat m Zero = (Succ Zero)
exponNat (Succ m) (Succ n) = (exponNat (Succ m) n) `multNat` (Succ m)

instance Eq Nat where
    Zero == Zero = True
    Zero == Succ n = False
    Succ m == Zero = False
    Succ m == Succ n = (m==n)

    Zero /= Zero = not(Zero == Zero)
    Zero /= Succ n = True 
    Succ m /= Zero = True 
    Succ m /= Succ n = not(m==n)

instance Ord Nat where
    Zero < Zero = False
    Zero < Succ n = True
    Succ m < Zero = False
    Succ m < Succ n = (m= Zero = True 
    Zero >= Succ n = False 
    Succ m >= Zero = True 
    Succ m >= Succ n = not(m Zero = False
    Zero > Succ n = False 
    Succ m > Zero = True 
    Succ m > Succ n = (m>n)
    
    Zero <= Zero = True 
    Zero <= Succ n = True 
    Succ m <= Zero = False 
    Succ m <= Succ n = not(m>n)

    max m n = if m > n then m else n
    min m n = if m < n then m else n

subNat :: Nat -> Nat -> Nat
subNat m Zero = m
subNat (Succ m) (Succ n) 
    | (Succ m) < (Succ n) = undefined
    | otherwise = subNat m n

factNat :: Nat -> Nat
factNat Zero = Succ Zero
factNat (Succ m) = (Succ m) `multNat` (factNat m)

fibNat :: Nat -> Nat
fibNat Zero = Succ Zero
fibNat (Succ Zero) = Succ Zero
fibNat (Succ (Succ m)) = (fibNat (Succ m)) `plusNat` (fibNat m)

infinity :: Nat
infinity = Succ infinity

---
不知道這篇會不會破壞版面 XD。

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。

Haskell Learning Note(3)

試論curring

在Haskell中，不用C++這麼複雜的方法來解決問題，而是採用curried function來解決這個問題。

Prelude> let add x y = x + y   -- 簡單來說就是寫一個 (+)
Prelude> :t add
add :: (Num a) => a -> a -> a   -- 此時的add是一個具有兩個引數的function
Prelude> :t add 1
add 1 :: (Num t) => t -> t        -- 此時的add 1 是具有一個引數的function
Prelude> :t add 1 2
add 1 2 :: (Num t) => t          -- 此時的add 1 2是一個不具有引數的function

在Haskell裡，使用單純的curried function即可解決，寫起來很像C++的function default arguemnt，意義不太一樣，在Haskell裡是真的把引數代入形成一個新的function，其實+ operator也可以做出同樣的功能(Josh Ko說這是語法糖XD)

Prelude> :t (+)
(+) :: (Num a) => a -> a -> a
Prelude> :t (1+)
(1+) :: (Num t) => t -> t
Prelude> :t (1+2)
(1+2) :: (Num t) => t

寫到這裡我在想，我幹麻沒事自己寫一個add呢 XD那麼，可以試著用map寫出一點有趣的東西

Prelude> map (1+) [1..10]
[2,3,4,5,6,7,8,9,10,11]

當然，一個curried function在FP中的功用不止於此，curried funciton可以做更多事，隨你寫，隨你造，而不用C++ STL裡的bind2nd這種相較之下較不直覺的方法。curried fuction的好處是在Haskell底下是lazy evaluation，也就是說，你function引數可以不用給全，直到你要求把答案算出來的那一刻把argument給全就行了，而且可以隨你組合，隨你寫，可以做出相當多的靈活變化，也就是說，curried function並非要求一次把function arguement給齊，在Haskell底下大部分的funciton都是curried function。

那麼有沒有要求要一次給齊的，換個腦子想想，就是uncurried function，在這樣子的一個function底下，沒有一次給足所有的argument就會出錯(一時想不到有什麼function)。

補充:當我們寫(1+)而我們又呼叫這個function時，是類似C++的default argument還是wrapper function的技法呢，如果記得是沒有錯，是前者，也就是說，不管怎麼compose，都是只有一層的呼叫，相當的方便。

---
真糟，寫的真少。

Haskell Learning Note(3) - 前傳

我本來想要參考和Josh Ko的MSN對話紀錄來這一篇的，但是發現MSN對話紀錄竟然不見了...Orz

funciton interface如何改變

一個function，會有0個至多個不等的argument，而function只有一個signal output(當然也不一定是signal output，你可以說傳一個list出來，說我傳了一堆東西，但是就整體而言，你還是傳了一個符合某一個type的東西出來)，這對 functional programming更是如此，基本上就算是function name相同但是arguments 個數不同的話，我們仍視為不同的function

先跳回C/C++，眾所皆知，C++有著function overloading機制(靠著compile-time決定呼叫那一個function，為一個static-linking)，基本上靠著這樣子的機制，避免非常多的name collision。

題外話，C++靠著三種機制來避免name collision，一種是name scope，一種是funciton overloading，一種是polymorphism，不過很可惜的是，沒有類似Java裡的inner class來避免一次性的class使用，但是到了boost，有提供lambda calculus來解決部分的問題。

或許換個角度來想，程式碼複用性一直是一個很重要很重要的問題，以function層面而言，最常見的wrapper function

int add(int a, int b){
    return add(a, b, 0);
}

int add(int a, int b, int c){
    return a+b+c;
}

當然，這個程式在C++中可以更簡單的寫成

int add(int a, int b, int c=0){
    return a+b+c;
}

這些都是程式撰寫上的技巧，不足以掛齒，在寫程式的單純呼叫function時，引數是不足以構成問題的，可是call-back function上呢，在STL algorithm的比較呢，以STL的find_if為例。

template<lass InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last,
                     Predicate pred);

其中的Predicate要求傳入一個value type的變數，傳回bool，也就是說，如果你的function不是一個引數，是不符合Predicate的要求，那麼就無法變成find_if所能使用的function object。

STL所提供的解決方法有二，如果你要求剛好是function object adaptor和predefined function object組合起來可解決，那麼就使用組合技，第二個方法為，自行撰寫一個較為general function object ，再使用funciton object adaptor來改變一個function object的interface。舉個簡單的例子

std::find_if(u.begin(), u.end(), std::bind2nd(std::less<int>(), 0)); //尋找某個區間第一個小於0的數字。

我不能不說，我當初看到這樣子的寫法，我以為找到了救星，funciton可以玩組合技耶，而且這樣子的確解決了call back function的問題。

利用wrapper function或者是STL裡面的function object adapter或種種程式語言的技能的確可以改變一個function原本的interface，但是有沒有更好的方法? 有啊，不然我就白寫了，看到Haskell的方法之後，以前的我好傻好天真(大誤)~XD。

---
還沒進入正題XD

如何用Haskell寫出笨拙的99乘法表

目前想法如下。

mult_line x = map (x*) [1..9]
mult_table x = map mult_line [1..x]

之後，我在ghci中呼叫

*Main> mult_table 9
[[1,2,3,4,5,6,7,8,9],[2,4,6,8,10,12,14,16,18],[3,6,9,12,15,18,21,24,27],[4,8,12,16,20,24,28,32,36],[5,10,15,20,25,30,35,40,45],[6,12,18,24,30,36,42,48,54],[7,14,21,28,35,42,49,56,63],[8,16,24,32,40,48,56,64,72],[9,18,27,36,45,54,63,72,81]]

Haskell Learning Note(2)

欠稿很大，預估要寫到folder後才能停一下。

環境
建議是用ghc(The Glasgow Haskell Compiler)，大部分的環境都有提供binary，直接安裝即可，而ghci是一個互動介面，較為常用指令如下。

• :q 離開ghci
• :l xd.hs 載入某個module(Haskell副檔名為.hs)
• :r 重新載入module
• :e 編輯所載入的module的文字檔(我在mac上，預設是用vim開啟)

簡單的開始
如果撰寫了一個function，可以使用:t 來看其形別要求，舉個例子

Prelude> :t sum . map read . words
sum . map read . words :: (Read a, Num a) => String -> a

剛開始學習，學會看type是一件非常重要的事。然而，就此打住，想先講講一些別的東西

Just Function
在Haskell中最小的組成單位是function，想要表達一堆資料，可以用list(不知道對不對，不過倒是知道list沒有這麼簡單)，一個function必有其input 和 output，然而，我學習的第一個問題，怎麼樣得知input和output的要求為何，如果跟C++ STL一樣，use type as an argument，必有其限制，所以:t非常的重要(因為就是拿來看型別要求)，在Haskell裡，有著非常神奇的type system，有好幾次我問Josh，為什麼會如此時，卻超出我的範圍，以剛剛說的例子而言

Prelude> :t words
words :: String -> [String]
(yen3註：一個String為input，產生一個為String的List)

Prelude> :t read
read :: (Read a) => String -> a
(yen3註： 一個String為input，產生一個型別為a符合Read的要求)

Prelude> :t map
map :: (a -> b) -> [a] -> [b]
(yen3註: map是一個神奇的function，基本原理就是，input為一個list，output也是一個list，但是map會套用一個function，將list of a轉換到list of b，簡單的來說，就是對每個元素做同一個動作)

Prelude> :t sum
sum :: (Num a) => [a] -> a
(yen3註: input 為一個list，輸出後型別為a符合Num的要求)

接著再回來看看原來的例子

Prelude> :t sum . map read . words
sum . map read . words :: (Read a, Num a) => String -> a
(yen3註: 變的很明顯，輸入一個字串，而輸出一個型別為a符合 Read 和 Num，全部串起來做一次就會變成...)

Prelude> sum . map read . words $ "123 456"
579
(yen3註：把字串根據空白分開成為個一list，然後每個元素被讀取成某一個型別之後，sum把每個元素做一求和的動作。)


其實這一行沒有解釋的很清楚，何謂Read要求 ? 還有，轉型的時候為什麼要轉成a? 這就再說XD (因為我也不會XD) 其實就學到這裡的時候，可以猜到一件事，Haskell自己幫你做了非常多的事，很多事硬要推測到底，其實反正看不懂。看清楚一個function的要求為何，似乎變的很重要，看懂他的運作方式會更有趣

每次連載都不會寫太長，基本上都是利用專題空閒寫作，我就盡量寫啦XD

---
基本上這篇的註都是大膽的猜測，但是想不到要用什麼字XD

Haskell Learning Note(1)

原本想說要用什麼 Learing about fuctnional programming using Haskell 之類的標題，但是一則是標題太長，一則是，我沒這麼專業，受到Josh Ko幫忙甚多，如果有任何錯誤是我表達不好，如果你看的懂，請出門左轉到Joshsoft留言感謝XD

What? Why?
什麼是functional programming? 簡而言之，一個programming組成的最小元素為數學性的function，在真實世界中的數學函式是沒有任何side effect，也就是說，給你一個input就會產生一個output，中間不會改變其他事。所以就某種狀況而且，這種思維非常適合數學好的人學習(我數學不好XD)。

functional programming之所以紅不起來的原因有很多，主要原因有二，第一，比起現在大部分的主流語言都來的慢，第二，如果很習慣現代的主流語言，學FP就會很痛苦(我就是那一個...Orz)，但是誰都不能忽略FP本身強大的特性。在Erlang本身而言，善用了No side effect特性，以較為簡單的方法寫出平行程式。最重要的原因，現在的FP不再像以前一樣這麼慢了，但是良好的特性還是存在的。

Haskell是一個不怎麼紅而且推廣者也不打算讓他紅的語言，紅的FPL很多，Erlang, ML, F#都是，但是這些較紅的語言都允許一些現代主流語言的特性，反正都要踏入這個不紅的領域了，學比較純的東西或許比較有趣?

為什麼要學Haskell，最重要的原因，Haskell is a pure functional programming language，次要的原因，Josh Ko誘拐我成功了XD，如果夠純，或許我會從裡面學到非常多有趣的東西。

參考資料
基本上Haskell的參考資料中文的不是很多，入門的更少，看英文是一個比較好的方法，網站參考資料如下

• Haskell wiki: 官方網站
• RealWorld Haskell: 網路上放的是beta版本，讓大家提供意見
• Yet Another Haskell Tutorial: 一份pdf文件，不厚約200頁，值得一看
• 嵐達網: 為Josh的老師scm所主持的FP社群，請大家多多捧場XD

而我目前的參考書單只有兩本

• Introduction to Functional Programming using Haskell 2/e
• Real World Haskell

然後我都沒有看過XD

連載中XD

---
考慮要不要寫在GooglePage還是wiki上

訂書

剛剛透過在美國的姊姊訂了一本 Introduction to Functional Programming using Haskell只能說，便宜一點點，不過還是覺得天瓏的代訂價3227有點誇張。

---
耶~期待~XD

寫程式的胡言亂語

這是一篇有關programming的文章，不想看的可以跳過了XDXD，不過最近的我似乎很少寫這些文章。

最近一直在寫C# with .net compact framework，老實說，我一直被微軟的名詞搞的暈頭轉向，當我有問題只能靠著MSDN來解決的時候，有一種很深刻的無力感...不過我不得不說，Visual Studio .net 是一個很棒的軟體開發工具(雖然eating畫GUI時常常出現記憶體堆疊錯誤，她應該是畫太好...Orz)，這部分是專題兼比賽關係，所以我大概等到比賽之後才會提及可以提及的部分，如果中華電信有保密條款之類的，我也只能說聲抱歉啦。

所以我想要提及一些我最近覺得很有趣的部分。寫程式越久只會覺得自己越來越不會寫程式，最近的興趣著重在兩個大重點functional programming 和 Refactoring。

functional programming 最近頗有復活的傾向，據我粗淺的知道(轉錄自某個老師告訴我的故事)，上一次FP紅的時候是在一堆人瘋AI(Artificial Intelligence)時，Lisp是一個非常聞名的FPL，在1990年代附近一堆人在做這個題目，但是並不是有那麼實際的成果，結果做這類的題目變人人討打。FP其實專長並不止於此，就我的了解，讓你寫程式更像寫數學一樣，No side effect，lazy evaluation，等等之類的特性，使得近代的FPL極具威力，而跟現在主流的Imperative programming大異其趣，著實是一個讓我產生高度興趣學習的領域，據Josh Ko描述，有比較靠近主流的ML和pure FPL的Haskell，外加我自己所買的Erlang，我想我的學習會以後面兩個為主。到目前為止，我還是不會寫，或許過一陣子，可以自己試著寫出一堆有趣的東西。

舉個例子好了sum . map read . words $ "123 456"我當初看到這行程式碼我就哭了，這可是我第一次碰C寫的要死要活的題目，轉成簡單的C++ Code;

std::string s = "123 456";

s += " ";
int sum = 0, temp=0;
for(std::size_t i=0; i< s.length();i++){
    if(s[i]>='0' && s[i]<='9') temp = temp*10 + s[i]-'0';
    else{
        sum += temp;
        temp = 0;
    }
}

當然，上述的程式碼沒有做任何的最佳化寫法，不然可以用C的atoi()之類的function，重點是，再看一次FP的程式碼，光看字面就可以猜到程式的意思了(要了解沒那麼簡單，我被Josh Ko搞死了好久...Orz)，以後會盡量把自己學習寫FP的筆記放上來，我想我有很大的機率會喜歡上這種程式思維。

接下來回主流Imperative programming XD，昨天嘗試的把Refactoring從第二章推進到第八章，這是一本我很少數後會後悔大一沒有買來看的書(當初錯過Effective C++也沒那麼嚴重)，裡面提到種種的方法太漂亮了，從function level的Composing Method到Object之間的Moving Features Between Objects& Organizing Data等等的方法，給我在OOP上很多體悟，也再一次深深的了解自己基本功的不足，舉個例子而言，一般寫身份字號產生器時，最難處理的是每個英文數字所代表的數字，我在寫作時就提出了一個很簡單的方法

// normal writing
char c = 'a';
int value = 0;
if(c=='a') value = 10;
else if(c=='b') value = 11;
/*...*/

// better writing 
const int c_value[] = {10, 11 /*...*/};
char c = 'a';
int value = c_value[c-'a'];

這個方法在Refactoring也有收錄，名字為Substitute Algorithm(6.9)，Refactoring並不會改變程式所要表現為何，很多時候會把一個複雜的function拆成由許多小function所組合，由專家告訴你如何測試及重構出一個更好的程式，在看這本書時，是一個很棒的體驗，縱使自己原本就會復審自己所寫的程式碼，我想我還是會不定期的看看這本書，會給我什麼體悟

學習相關OOP的運用最大的問題是，我一定得知道這些事(Design Patterns, Refactroing ...)，但是我又得忘掉他，然後在需要的時候想起來，而不是為了運用而運用，但是我想，或許我會在Refactoring改變一下作法，或許我很難體會怎麼用Design Patterns，但是我想我會很樂意的使用Refactoring來學會Design Patterns，這時候就不得不提到 "重構-向範式前進(Refactoring to Patterns)"，我還沒閱讀，但是我覺得或許是一個行的通的閱讀。

還有很多想提的沒有提及，就下次再說吧。

---
好長的一篇XD