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