Home | 2013-04-30

学习Haskell

最近几个月利用上下班的时间在学习Haskell，Haskell有不少让人开阔思路的东西，也有不少看起来很美好，用起来不错，但是读起来费劲的东西。Haskell的语法学的差不多了之后，用Haskell写了一个简单的C++代码行统计工具，写过几个版本，留下了两个，一个是直接用模式匹配写的，一个是山寨了一个极简的parse combinator，然后用这个山寨的parse combinator写了一个版本，代码估计写的都比较烂，以后进阶学习之后有时间再改。这个统计工具并不是完整的处理C++的语法，也没对在字符串和宏定义里面的"//" "/*" "*/"做处理，因此对某些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，那它就满足Monadtypeclass中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的问题没之前想像的那么严重。）