最近幾個月利用上下班的時間在學(xué)習(xí)Haskell，Haskell有不少讓人開闊思路的東西，也有不少看起來很美好，用起來不錯，但是讀起來費(fèi)勁的東西。Haskell的語法學(xué)的差不多了之后，用Haskell寫了一個簡單的C++代碼行統(tǒng)計(jì)工具，寫過幾個版本，留下了兩個，一個是直接用模式匹配寫的，一個是山寨了一個極簡的parse combinator，然后用這個山寨的parse combinator寫了一個版本，代碼估計(jì)寫的都比較爛，以后進(jìn)階學(xué)習(xí)之后有時間再改。這個統(tǒng)計(jì)工具并不是完整的處理C++的語法，也沒對在字符串和宏定義里面的"http://" "/*" "*/"做處理，因此對某些C++程序統(tǒng)計(jì)代碼行，可能不完全正確，但是基本可以用。
data, type, newtype
Haskell里面用data來定義數(shù)據(jù)類型，它可以是這樣：
data Mode = ReadMode | WriteMode
data Some = Some Int String
data Thing = { a :: Int, b :: String }
data Func a b = { func :: a -> b }
第一行定義了一個Mode，包含ReadMode和WriteMode；
第二行定義了一個普通數(shù)據(jù)類型Some，包含一個Int數(shù)據(jù)和一個String數(shù)據(jù)；
第三行定義了一個普通數(shù)據(jù)類型Thing，包含類型為Int的a和類型為String的b；
第四行定義了一個符合數(shù)據(jù)類型Func，里面有個函數(shù)類型為(a -> b)的數(shù)據(jù)func。
第一種相當(dāng)于C++中的enum class，第二種第三種相當(dāng)于普通的struct數(shù)據(jù)，第二種和第三種的區(qū)別是第二種不能直接取到Int和String的數(shù)據(jù)，第三種可以通過a,b取到數(shù)據(jù)，第四種相當(dāng)于C++的template class(struct)，第四種寫成這樣來定義具體的數(shù)據(jù)類型：
type IntStringFunc = data Func Int String
type在這里定義了一個別名IntStringFunc類型，包含了一個函數(shù)類型是Int -> String的func的數(shù)據(jù)，這里的type相當(dāng)于C++ 11的using別名，因?yàn)樗€可以這樣寫：
type IntBFunc b = data Func Int b
在C++ 11中，using包含了typedef的功能，也支持了template class的類型typedef，如下：
template <typename T, typename P>
class SomeType;
template <typename T>
using SomeTypeInt = SomeType<T, int>;
newtype定義的數(shù)據(jù)類型跟type類型，不過type定義的純粹是別名，別名類型跟原始類型是一致的，而newtype則定義的是一個wrapper，是一種新的數(shù)據(jù)類型，所以是newtype。newtype定義的類型是編譯時期的wrapper，Haskell保證沒有運(yùn)行時期的開銷，newtype定義的跟data類似：
newtype NewType a b = NewType { func :: a -> b }
模式匹配
上面說道data定義的第二種數(shù)據(jù)類型，包含Int和String的數(shù)據(jù)，但是不能直接取到這兩個數(shù)據(jù)，所以我們需要定義兩個函數(shù)來取其中的數(shù)據(jù)：
some = Some 0 "test" -- 定義一個數(shù)據(jù)，類型為Some
-- 定義兩個函數(shù)用于獲取Some的數(shù)據(jù)
getSomeInt Some i _ = i
getSomeString Some _ s = s
getSomeInt some -- 0
getSomeString some -- "test"
這里的getSomeInt和getSomeString函數(shù)都是采用模式匹配來實(shí)現(xiàn)，模式匹配就是把數(shù)據(jù)的結(jié)構(gòu)直接寫在代碼中來匹配，然后取出想要使用的數(shù)據(jù)即可。
Haskell里常用的Maybe數(shù)據(jù)類型是這樣定義的：
data Maybe a = Nothing
| Just a
如果要取用Maybe里面的值，我們通常使用模式匹配來獲取數(shù)據(jù)，如下：
useMaybe maybe =
case maybe of
Nothing -> … -- Maybe的值是空
Just a -> … -- 直接使用a即可
useMaybe (Just 1)
下面調(diào)用useMaybe的函數(shù)體內(nèi)取到的a的值就是1。
Haskell里的內(nèi)置數(shù)據(jù)類型list，比如[1, 2, 3, 4]，使用:可以把新的元素添加到list頭部，即：
0 : [1, 2, 3, 4] -- [0, 1, 2, 3, 4]
這樣的特性同樣可以簡單的套用在模式匹配上面，如下：
useList [] =
useList (x:xs) = … -- x是list里面的第一個元素，xs是list的尾部
模式匹配可以很直觀的匹配數(shù)據(jù)的原始表示方式，并可以取出其中有用的值做其他操作，它是一個簡單直觀有效的操作數(shù)據(jù)的方式，甚至可以在嵌套很深的tuple數(shù)據(jù)里面直接取出想要的數(shù)據(jù)，而不用像C++那樣調(diào)用tuple::get之類的函數(shù)來取出其中的值，比如：
getTupleValue (_, _, _, (_, _, (x:xs))) = … -- 取得x和xs數(shù)據(jù)
Visitor模式和C++ template
王垠說設(shè)計(jì)模式中值得一提的模式不多，其中之一的visitor模式是在模擬模式匹配。visitor模式通常是訪問獲取某個繼承類層次構(gòu)成的一個樹形結(jié)構(gòu)中的某個節(jié)點(diǎn)的具體類型，并對這種具體類型做某些操作，而模式匹配是可以從復(fù)雜的數(shù)據(jù)結(jié)構(gòu)中直接取出想要的數(shù)據(jù)。
C++的template meta-programming也可以看成是一種模式匹配，C++里面著名的Factorial求值是這樣的：
template <int N>
struct Factorial
{
enum { value = N * Factorial<N - 1>::value };
};
template <>
struct Factorial<0>
{
enum { value = 1 };
};
int v = Factorial<10>::value;
而這段代碼如果用Haskell寫是這樣的：
factorial 0 = 1
factorial n = n * factorial (n - 1)
v = factorial 10
C++中的模板參數(shù)就是用來做模式匹配的，每特化一種類型就可以匹配某種類型，然后對那種匹配的類型做相應(yīng)的操作。C++的template meta-programming是編譯時期（編譯器運(yùn)行期）的行為，所以它只能操作類型以及編譯時期能夠確定的值，而模式匹配是程序本身的運(yùn)行期的行為。
Currying
Haskell的Currying是一個很有用的特性，但是我覺得這個特性濫用的話，也會讓程序代碼的可讀性降低不少。所謂Currying就是可以向一個多參數(shù)的函數(shù)傳遞比它所需的參數(shù)個數(shù)更少的參數(shù)后返回生成的一個新函數(shù)接受剩余的參數(shù)的函數(shù)。Haskell里的函數(shù)默認(rèn)都是curried的，所以Haskell里面的函數(shù)可以隨意currying，比如：
add :: Int -> (Int -> Int) -- 一般寫成 Int -> Int -> Int
add a b = a + b
addOne :: Int -> Int
addOne = add 1
addOne 2 -- result: 3
Currying的實(shí)現(xiàn)是使用的單參數(shù)的lambda構(gòu)成的閉包(closure)，add可以看成是接受一個Int參數(shù)返回一個函數(shù)，這個函數(shù)的類型是Int -> Int。
Partial application
Currying是一個從左到右部分傳參數(shù)的一個過程，也就是不會出現(xiàn)參數(shù)a還沒給，就給了具體的參數(shù)b的情況。如果確定要先給參數(shù)b，那么它是Partial application，如下：
addTwo a = add a 2
addTwo 1 -- result: 3
(+ 2) 1 -- result: 3
(+ 2)這種類似的用法可能會作為參數(shù)傳遞給另外一個函數(shù)。Partial application是一種更寬泛的概念，上面的Currying是一種Partial application。
正如王垠所說的，如果一個函數(shù)接受了多個參數(shù)，但是這個函數(shù)在實(shí)際調(diào)用中被Currying了很多次，那最后生成的那個函數(shù)它到底接受幾個參數(shù)是不能很直觀的看明白的，比如：
func a b c d e f = …
do1 = func 1
do2 = do1 2
do3 = do2 3
do4 = do3 4
do5 = do4 5
那當(dāng)我們看到do5函數(shù)的時候，我們是很難判斷do5到底接受幾個參數(shù)，尤其是do5跟前面幾個doN函數(shù)不在同一個地方定義，很有可能do5只是傳遞給某個函數(shù)的參數(shù)，當(dāng)然如果給每個函數(shù)都加上函數(shù)類型聲明會清晰許多。當(dāng)Currying碰到了flip之后，那代碼的可讀性會降低更多，所以我覺得Currying是一個很有用的特性，但是如果被濫用的話，那代碼的可讀性會是一個問題。
C++: function + bind
C++中的function + bind其實(shí)是一種Partial application實(shí)現(xiàn)，比如：
int Func(int a, int b, int c);
std::function<int (int, int)> f1 = std::bind(Func, 1, std::placeholders::_1, std::placeholders::_2);
std::function<int (int)> f2 = std::bind(f1, std::placeholders::_1, 3);
f2(2); // Func(1, 2, 3);
我覺得C++的function + bind會比Currying的可讀性要好一些，畢竟我們可以完整看到f1和f2的函數(shù)類型，知道參數(shù)類型及個數(shù)和返回值，是有利于代碼的可讀性的，當(dāng)然這里完全可以不寫出f1和f2的類型，采用auto，我們同樣可以從調(diào)用函數(shù)bind的placeholder的個數(shù)得知bind之后的function的參數(shù)個數(shù)，這樣我們可以不用看到函數(shù)Func的聲明，就知道需要傳幾個參數(shù)。function + bind跟Currying一樣會影響代碼的可讀性，如果嵌套的層次越多，可讀性就越差，所以使用這些特性的時候不要過度。
typeclass
Haskell用typeclass來表示一個concept，它是一組抽象函數(shù)的集合，一個滿足某個typeclass的數(shù)據(jù)類型，它就可以跟其他使用這個typeclass的函數(shù)或者數(shù)據(jù)類型組合使用。typeclass一般這么定義：
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
return :: a -> m a
fail :: String -> m a
它定義了一個叫Monad的typeclass，這個typeclass的concept里有四個函數(shù)，分別是(>>=), (>>), return和fail，m是一個帶類型參數(shù)的數(shù)據(jù)類型。我們上面知道了Maybe是一個帶類型參數(shù)的data類型，它定義如下：
data Maybe a = Nothing
| Just a
既然Maybe是一個帶類型參數(shù)的data，那它就滿足Monad typeclass中m的需求，因此可以把Maybe定義成Monad，如下：
instance Monad Maybe where
(>>=) maybeA f =
case maybeA of
Nothing -> Nothing
Just a -> f a
(>>) maybeA maybeB = maybeA >>= (\_ -> maybeB)
return = Just
fail = error
這里(\_ -> maybeB)定義了一個lambda，參數(shù) _ 緊接 \，-> 后面則是函數(shù)體。函數(shù)(>>)和fail是可以作為默認(rèn)實(shí)現(xiàn)放到class Monad的定義里面，而instance Monad的時候只需要實(shí)現(xiàn)(>>=)和return即可。
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
(>>) ma mb = ma >>= (\_ -> mb)
return :: a -> m a
fail :: String -> m a
fail = error
對于內(nèi)置list類型[a]，也是帶有一個類型參數(shù)a，因此，我們同樣可以把[] instance成為class Monad，如下：
instance Monad [] where
(>>=) (x:xs) f = (f x) ++ (xs >>= f)
(>>=) [] _ = []
return a = [a]
函數(shù)(>>)和fail我們保留默認(rèn)的實(shí)現(xiàn)即可。
Monad
上面實(shí)現(xiàn)的定義的typeclass就是Haskell著名的Monad，它是組合其他操作的一個基礎(chǔ)typeclass，是與no pure交互的一個重要媒介。一般情況下Monad有兩種，一種是數(shù)據(jù)wrapper，一種是action的wrapper。上面定義的Maybe Monad和list Monad都是數(shù)據(jù)類型的wrapper，它們實(shí)現(xiàn)了Monad定義的接口函數(shù)，我們還可以將其它data instance成Monad，只需要遵循了Monad的接口即可。
我們知道Haskell的函數(shù)都是pure的，沒有任何狀態(tài)的函數(shù)，但是與現(xiàn)實(shí)世界交互必然需要影響或修改某種狀態(tài)，并且會需要順序執(zhí)行某些操作以完成交互。我們把a(bǔ)ction操作封裝在一個data里面，并讓它instance Monad，為了讓前一個action的結(jié)果值作為某種狀態(tài)往下傳遞，Monad的(>>=)就是為了這個目的而存在的，(>>=) 函數(shù)的類型是 m a -> (a -> m b) -> m b，它的意思就是執(zhí)行封裝在m a這個數(shù)據(jù)里面的action，然后把這個action的結(jié)果值做為參數(shù)傳遞給(>>=)的第二個參數(shù)(a -> m b)，第二個參數(shù)是一個函數(shù)，這函數(shù)可以取用第一個參數(shù)的結(jié)果，再返回一個m b的數(shù)據(jù)，m b的數(shù)據(jù)也是一個action的封裝，這樣當(dāng)一連串的(>>=)放到一起的時候，就可以把一個狀態(tài)值作為action的參數(shù)和結(jié)果值往下傳遞。
從Monad的函數(shù)(>>)的實(shí)現(xiàn)我們可以看到，它把m a的action的結(jié)果值丟棄直接返回了m b，當(dāng)一連串的(>>)放到一起的時候，其實(shí)就是讓一組action順序執(zhí)行。通過(>>=)和(>>)，可以把一組Monad action data組合起來。
IO Monad
IO Monad是一個把IO action封裝的data，我們可以使用IO Monad與外界進(jìn)行輸入輸出交互，下面是一個"hello world"：
helloWorld = do
putStr "hello "
putStrLn "world"
這里do語法糖其實(shí)就是用的Monad來實(shí)現(xiàn)，展開之后是這樣：
helloWorld =
(putStr "hello ") >>
(putStrLn "world")
由(>>)函數(shù)確定(putStr "hello ")和(putStrLn "world")需要是同一個Monad類型，我們可以查詢到putStr和putStrLn的類型是String -> IO ()，那么(putStr "hello ")和(putStrLn "world")的類型都是IO ()，helloWorld函數(shù)把兩個IO ()的action數(shù)據(jù)順序組合起來生成一個新的IO ()，當(dāng)這個helloWorld IO action被執(zhí)行的時候，它會依次執(zhí)行封裝在它里面的IO action。我們可以把helloWorld IO action放到Main函數(shù)里面然后編譯執(zhí)行，也可以直接在ghci里面執(zhí)行。
我們可以自己定義某種data再instance Monad，這樣可以構(gòu)成一組data combination，可以實(shí)現(xiàn)任意的action combine。我山寨的極簡的parse combinator的數(shù)據(jù)類型定義如下：
newtype Parser a = Parser {
runP :: State (ByteString, Context) a
} deriving (Monad, MonadState (ByteString, Context))
這里Parser帶一個類型參數(shù)a，deriving (Monad, MonadState (ByteString, Context))表示編譯器自動instance Monad和instance MonadState (ByteString, Context)。有了這個Parser之后，可以寫出簡單的幾個combinator，然后使用這幾個combinator組合成更加復(fù)雜的，組合的過程就是利用了Monad的組合能力。當(dāng)所需的combinator都實(shí)現(xiàn)了好了之后，可以最終實(shí)現(xiàn)一個Parser a來分析整個C++文件：
file = repeatP $ spaceLine <||> normalLine
file就把分析整個C++文件所需的操作都combine到了一起，有了這個分析整個文件的Parser a之后，需要把它跑起來，那就需要定義下面這個函數(shù)：
runParse :: Parser a -> ByteString -> (a, (ByteString, Context))
runParse p b = runState (runP p) $ (b, emptyContext)
這個函數(shù)接受一個Parser a和一個文件內(nèi)容ByteString作為參數(shù)，把整個Parser a封裝的action用于分析文件內(nèi)容，再產(chǎn)生一個分析結(jié)果。
這里的file，它是一個一個小的combinator構(gòu)成的，每個combinator是一個action加上它所需數(shù)據(jù)構(gòu)成一個“閉包”再存放到Parser a的data里面，其實(shí)可以認(rèn)為實(shí)現(xiàn)了Monad的數(shù)據(jù)類型是一個“閉包”的載體。在其它語言里，我們可以使用閉包來實(shí)現(xiàn)combinator，我記得兩年半前，我使用lua的閉包實(shí)現(xiàn)了一組游戲副本內(nèi)容玩法操作的combinator，這些閉包自由組合在一起之后就能完成一個副本中所需的玩法操作。
Monad transformer
一種Monad類型只能封裝和組合一種action操作，而與外界交互的時候，很多時候一種Monad類型是不夠的，為了讓多種Monad類型組合在一起，就需要定義Monad transformer，它跟Monad一樣也是一個數(shù)據(jù)類型，不同的是它接受至少兩種類型參數(shù)，其中一種就是Monad的類型，這樣就可以把某個Monad類型嵌套在它里面。
newtype StateT s m a = StateT {
runStateT :: s -> m (a, s)
}
這里StateT就是一個Monad transformer，它允許嵌套一個Monad m類型，它是typeclass MonadState的一個instance，MonadState如下：
class Monad m => MonadState s m | m -> s where
get :: m s
put :: s -> m ()
為了讓Monad transformer可以嵌套進(jìn)StateT，其它類型的Monad transformer就需要instance MonadState，而StateT Monad transformer為了可以嵌套在其它Monad transformer中，就需要對其它Monad transformer抽象出來的typeclass instance，符合這種規(guī)則的Monad transformer就可以相互之間嵌套了，嵌套的層次可以任意深，這樣構(gòu)造出來的Monad里面有個Monad transformer stack，而這個新構(gòu)造出來的Monad就可以使用多種Monad的action操作組合在一起了。
Monad transformer會帶來一個問題，如果想定義一個新的Monad transformer，需要先抽象出這個Monad transformer的typeclass，就像MonadState typeclass一樣，然后把其它Monad transformer都instance這個新抽象出來的typeclass，這樣才能讓這個新的Monad transformer嵌套在其它的Monad transformer之中，接著，為了讓其它Monad transformer能夠嵌套在新的Monad transformer之中，需要把新的Monad transformer instance其它Monad transformer抽象的typeclass。
我覺得其實(shí)Haskell為什么會有Monad和Monad transformer的存在，是因?yàn)镠askell是一個純函數(shù)式語言，它本身沒有順序執(zhí)行語句的能力，為了能讓Haskell擁有修改外部狀態(tài)并能夠順序執(zhí)行語句的能力，引入了Monad，又為了讓多種action的Monad能夠組合到一起，由于Monad是一個data type，它不能簡單的組合到一起，因?yàn)轭愋筒灰恢拢瑸榱俗屗鼈兘M合到一起，又引入了更一般化的Monad transformer，讓這些Monad transformer嵌套在一起構(gòu)成一個stack，才能將這些不同類型的Monad組合。
Lazy evaluation
Haskell里面使用的是惰性求值方式，王垠說Haskell的惰性求值是一個很嚴(yán)重的問題。我目前也覺得惰性求值是一種負(fù)擔(dān)，因?yàn)槎栊郧笾担瑫沟贸绦蚝苋菀拙统霈F(xiàn)space leak，我寫的那兩個版本的統(tǒng)計(jì)C++代碼行工具都有這個問題，因?yàn)樗嵌栊郧笾担运鼤颜麄€目錄的數(shù)據(jù)全部取出來構(gòu)造存放到內(nèi)存中，最后再進(jìn)行求值，這就自然導(dǎo)致統(tǒng)計(jì)大量C++代碼文件的目錄時，占用內(nèi)存會很高（幾百M(fèi)上G），也許當(dāng)我進(jìn)一步學(xué)習(xí)之后，我能夠避免這種space leak，但這對于一個初學(xué)Haskell的人是一個不小的負(fù)擔(dān)，因?yàn)殡S便寫一個小程序都有可能耗用幾百M(fèi)的內(nèi)存，而用其他語言實(shí)現(xiàn)的話，內(nèi)存很容易很自然的控制在幾M之內(nèi)。（看完優(yōu)化章節(jié)，只對程序修改了幾行代碼就讓內(nèi)存使用降到可以接受的程度，看來Lazy evaluation的問題沒之前想像的那么嚴(yán)重。）
posted on 2013-04-30 20:41
airtrack 閱讀(5502)
評論(0) 編輯 收藏 引用