Haskell 函数式编程

Haskell是纯函数式编程，它强调不函数不改变外部世界状态，即，一个函数的输出只由函数接收的输入决定。那如何与外面沟通呢，比如读取一个文件内容并输出这个文件内容（字符串），显然这种函数非纯函数，因为它的输出是会随着文件内容改变而改变。Haskell在纯函数与外部世界之间建立了一扇门，即Monad，这部分内容以后再介绍。

（本文例子多来自real world haskell，原因是这本书给的例子太经典）

1. 与外部世界交流

首先给出一个例子如下，这个函数用于读取输入文件，并作一些处理，然后输出到另一个文件中

--file: Interact.hs
import System.Environment (getArgs)

interactWith function inputFile outputFile = do
    input <- readFile inputFile
    writeFile outputFile (function input)

main = mainWith myFunction
    where mainWith function = do
              args <- getArgs
              case args of
                  [input, output] -> interactWith function input output
                  _ -> putStrLn "error: two parameters needed"
          myFunction = tail

注意每一行的字符缩进。

这段代码中myFunction就是对输入文件的内容进行处理的函数，这里是tail函数，也可以改成其他的，只要函数原型满足String -> String即可。

测试这个源代码

> ghc --make Interact
> cd [target path]
> Interact in.txt out.txt

如果目标同级目录中in.txt文件内容为"中文测试"，那执行后，out.txt文件内容为"文测试"。

2. 通用分行

我们知道Windows和Unix类系统的换行符不同，分别为” ”，” ”或” ”，而Windows上编写的Haskell源码可能会拿到Unix类系统上编译，那么，比如分行处理就会出问题。

现在我们写一个能解决这个困境的方法，思想是遇到关键字符时进行切断，代码如下

-- file: SplitLines.hs

splitLines [] = []
splitLines cs = 

    let (pre, suf) = break isLineTerminator cs

    in pre : case suf of

                 (‘
’:’
’: rest) –> splitLines rest

                 (‘
’: rest) –> splitLines rest

                 (‘
’: rest) –> splitLines rest

                 _              -> []

isLineTerminator c = c == ‘
’ || c == ‘
’

这段代码一目了然。对case的几种情况，顺序是否重要呢。答案是不重要，可以自行测试一下。

Haskell提供了一个分行函数line，以及一个将字符串List合并成一个字符串，其中原来List中的每个字符串末尾添加一个换行符。

3. 中缀函数

函数名置于参数中间，而普通的函数则是前缀函数（函数名置于参数前）。写中缀函数方法是在函数名两边加 ` 号（键盘上数字1左边的那个键）

-- file: InfixFun.hs

a `cons` b = a : [b]

data a `With` b= a `With` b
                 deriving (Show)

使用时，如果函数名置于参数中间则需要在两边加 ` 号，如果置于参数前，则不需要。

注意上面的函数”cons”与Prelude包里的concat不同，concat的原型为[[a]] –> [a]，是将输入的各个list合并成一个list。

4. 递归函数

学习Haskell过程中会经常接触，这里不再具体展开，只说一下尾调用优化(tail call optimization)，因为函数式语言中没有循环，而是采用递归调用函数自身，这样每次调用时都分配一些内存空间，一般来说这会导致内存占用的线性增长，然而函数式语言的实现一般会检测尾递归然后转换使得在一个不变的内存空间中进行尾递归调用。

大部分命令式语言实现在进行循环时也是在一个不变的内存空间中执行循环体，但是很少有实现尾调用优化，这也是为什么在命令式语言中进行函数式编程导致内存泄漏或者性能很差。（事实上，部分命令式语言进行了TCO，实现尾递归性能不会明显下降，具体情况可以专门去研究一下）

5. 高阶函数

介绍几个高阶函数，所谓高阶函数就是其参数包含另一个函数，类似数学中f(g)。

a) map :: (a –> b) –> [a] –> [b]，map函数接收两个输入参数，一个函数f以及一个list，对这个list中的每个元素应用这个函数f，然后得到b，最后返回b的list。

b) filter :: (a –> Bool) –> [a] –> [a]，用指定函数筛选一个list中满足条件的元素

c) 对一个集合计算出一个值(reduce)，这里给出一个书中的例子，Adler32算法，有关Adler32可自行搜索。

-- file: Adler32.hs

import Data.Char (ord)

import Data.Bits (shiftL, (.&.), (.|.))

base 65521

adler32 xs = helper 1 0 xs

    where helper a b (x:xs) = let a’= (a + (ord x .&. oxff)) `mod` base

                                  b’= (a’+ b) `mod` base

                              in helper a’b’ xs

          helper a b _      = (b `shiftL` 16) .|. a

我们可以将这些行为抽象到一个高阶函数：对一个list的每一项做一些事情，然后更新累加器，直到处理完所有list项后，返回这个累加器。有点类似将一维的list折叠起来成为一个点有木有？这种类型的函数在Haskell中称为fold。

d) left fold，从list的左边开始折叠

foldl :: (a –> b –> a) –> a –> [b] –> a

开始，函数对累加器种子a0和list第一个项b[0]进行计算得到a1，然后函数对a1和list下一项b[1]计算得到a2，如此知道取完list最后一项，最后返回累加器的值an。比如计算一个整型list各项的和，可以写成如下

-- file: Sum.hs

sum :: [Integer] –> Integer

sum xs = foldl (+) 0 xs

e) right fold，从list的右边开始折叠

foldr :: (a –> b –> b) –> b –> [a] –> b

f) fold实例

这个函数其实也很简单，就是从list的尾部取值a[n-1]然后与累加器种子b0计算得到b1，然后取list倒数第二个值a[n-2]与b1计算得到b2，依次直到取list的第一个值a[0]与bn-1计算得到bn，注意这里b后面的数字是下标。

别看foldr好像只是简单的从右折叠，其实用途还是很大滴，比如，最终计算得到一个列表时，则使用foldr，原理很简单，因为连接成为list总是在一个已有的list前面加一个元素，即

a1:[a]

并且，我们可以使用foldr来实现foldl，这是原书上的一个例子，初看确实如作者所说让人非常头疼不容易理解，这里给出这个例子并稍作解释。

-- file: MyFoldl.hs

myFoldl :: (a –> b –> a) –> a –> [b] –> a

myFoldl f z xs = foldr step id xs z

    where step x g a = g (f a x)

一开始本人看这个函数的时候也是有点懵逼了，虽然原作者没有解释但是却给出提示”函数柯里化，通过:type id查看id的签名”。

如果看到局部函数step的定义，知道step接收三个参数，而myFoldl函数体中，foldr后面恰好跟着三个变量，如果把这三个变量当作step的三个输入参数，那就不可能理解这个函数了。好吧，我承认这里说了这么多废话，无非是不想提前剧透，给读者一个自行思考的空间，下面开始解释：

函数的优先级最高，foldr那一行没有小括号，故从左往右执行，foldr接收三个参数，一个函数step，某一个类型参数id，以及一个列表xs，通过:type id 可以知道id是一个函数，查阅haskell API文档也可以知道这是一个返回自身的函数，原型为a –> a，所以，在本上下文中，

id:: (a' –> a')

xs:: [b]

step:: b –> (a' –> a') –> (a' –> a')

foldr:: (b –> (a' –> a') –> (a' –> a')) –> (a' –> a') –> [b] –> (a' –> a')

写了这么一大段，其实只要把 (a' –> a') 看成 a 就可以了，然后，foldr将xs中从末尾开始每一项bk（k为下标）和累加器值 idk（k为下标）作为step的输入参数，然后得到一个中间返回值为idk+1（k+1为下标）

-- foldr 定义如下

foldr step zero (x:xs) = step x (foldr step zero xs)

foldr _ zero [] = zero

-- 本上下文中

foldr step id xs 

    == step xs[0] (foldr step id xs')

    == step xs[0] (step xs[1] (foldr step id xs''))

    == step xs[0] (step xs[1] (… (step xs[n-1] id)…))

-- 返回结果类型

foldr step id xs :: (a' –> a')

-- 柯里化

foldr step id xs z = (foldr step id xs) z

                   = step xs[0] (step xs[1] (…(step xs[n-1] id)…)) z                     （*）

到这里，就能对应上myFoldl函数体中局部函数step的定义了，如下

step :: b –> (a' –> a') –> a –> a

step x g a = g (f a x)

-- 对比(*)式得知

-- 第一次计算时

x = xs[0]

g = step xs[1] (…(step xs[n-1] id)…))

a = z

-- 第二次计算时

x = xs[1]

g = step xs[2] (…(step xs[n-1] id)…))

a = f a xs[0]

-- 第三次计算时

x = xs[2]

g = step xs[3] (…(step xs[n-1] id)…))

a = f (f a xs[0]) xs[1]

-- ……

-- 最后myFoldl的计算表达式为

myFoldl = f (…(f a xs[0])…) xs[n-1]

-- end

g) fold空间泄漏(space leaks)

通过前面分析，我们看到fold在计算过程中其实嵌套了很多表达式，一层一层地，事实上，最终只有在需要表达式的值时候，才会计算表达式结果。在计算式的值之前，表达式被存储为一个thunk（关于thunk可以上网搜索其含义），然而不幸的是，存储thunk比存储值占用太多空间了，而我们知道栈空间有限，所以在thunk大到一定程度会导致异常，比如

ghci> foldl (+) 0 [1..1000000]

这个thunk包含了100000个整形和99999个 (+)应用，这会占用很大的内存，事实上，在计算这个表达式值的时候确实引发了异常。解决的方案是使用Data.List模块中定义的 fold' 函数，它跟 fold 类似，但是不会建立thunk，使用如下：

ghci> :m +Data.List

ghci> foldl' (+) 0 [1..1000000]

500000500000

h) 匿名（lambda）函数

lambda函数以一个反斜线()开头，后面跟函数参数，然后跟 (->)，然后跟函数体，比如上一部分的myFoldl函数可以写成这样，

myFoldl f z xs = foldr (x g a –> g (f a x)) id xs z

然而，一个函数能写成lambda的前提是这个函数只有一个子句，如果有多个子句，比如head函数就不可以

unsafeHead = (x:_) –> t

显然没有考虑到参数为 [ ] 的情况。事实上，在很多场合，一般都避免使用lambda表达式，因为那样导致代码可读性不高。

i) As-Patterns

对参数使用@符号，后面跟模式，比如

suffixes :: [a] –> [[a]]

suffixes xs@(_:xs') = xs : suffiex xs'

suffixes _ = []

这个例子中，如果@后的模式匹配成功，则xs被绑定到模式中，xs' 被绑定到xs的除去首项的列表，虽然也可以不使用@，如下

suffixes1 :: [a] –> [[a]]

suffixes1 (x:xs) = (x:xs) : suffiex1 xs

suffixes1 _ = []

但是，使用As-patterns，在递归调用时，参数是共享而非复制，我们知道复制会导致分配新的内存，虽然这个代价并不高。

j) 组合函数

可以将几个函数组合起来，比如

compose :: (b –> c) –> (a –> b) –> a –> c

compose f g x = f (g x)

其实这个compose函数的作用仅仅是将原先需要加小括号改变运算优先级的情况封装，从而使得函数参数 f g x 不加小括号的依次写出来。

幸运的是，haskell中不需要我们定义这样一个compose函数，Prelude包中已有一个这样的函数 (.)，用法就是 h = f . g，这样给函数h一个输入 x 时，记住先对 x 应用 g 函数，然后应用 f 函数。

k) 空间泄漏和严格计算

尽量保证在构建一个list时，使用foldr，并用 foldl' 代替foldl ，那么实践中，空间泄漏就不太可能困扰我们。

由于 foldl' 是一个严格计算的，而不像 foldl 是延迟计算，foldl' 通过使用 seq 的一个函数来避开haskell的延迟计算特征，参见代码

-- 给出foldl'的签名

foldl' :: (a –> b –> a) –> a –> [b] –> a

foldl' _ zero [] = zero

foldl' step zero (x:xs) =

    let new = step zero x

    in  new `seq` foldl' step new xs

其中，seq函数原型为 seq :: a –> t –> t，seq的引入就是为了获得严格特性(strictness)，seq有两个输入参数，类型不定，并返回第二个参数值，具体可上网搜索seq详情。

当seq计算时，在seq返回值之前，它强制其参数先被计算出来。每一次利用 step zero x 计算出值之后再传给foldl' 。

使用seq的坑还是蛮多的，比如下面这个例子就是一个不好的用法

badfoldl' _ zero [] = zero

badfoldl' step zero (x:xs) =

    seq (step zero x)

        (badfoldl' step (step zero x) xs)

这里，代码意图是想严格计算 step zero x 的值，然而第一个 step zero x 表达式的值被严格计算出来，与第二个 step zero x 的值没有关联。当第一个表达式值计算出来的时候，seq返回第二个表达式，而第二个表达式 step (step zero x) xs) 中的 step zero x 被没有被严格计算出来。

最后，需要指出的是，seq也不是完全有利的，比如它导致运行时检查表达式是否被严格计算出来。总之，seq的坑，以后需要专门填一下。