《Real World Haskell》笔记（4）：函数式编程

一个简单的命令行程序

-- file InteractWith.hs
import System.Environment (getArgs)

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

main = mainWith myFunction
  where mainWith function = do
          args <- getArgs
          case args of
            [inputFile,outputFile] -> interactWith function inputFile outputFile
            _ -> putStrLn "error: exactly two arguments needed"

        --replace id with other function below when you need
        --id 函数接受一个值，并原封不动地返回这个值
        myFunction = id

• 该接口程序读入一个文件，将函数应用到文件，并且将结果写到另一个文件
• do 关键字引入一个块，标识那些带有副作用的代码，比如对文件进行读和写操作，被 do 包围的 <- 操作符效果等同于赋值

分离多行文本

-- file SplitLines.hs
splitLines [] = []
splitLines cs =
    let (pre, suf) = break isLineTerminator cs
    in  pre : case suf of
                ('\r':'\n':rest) -> splitLines rest
                ('\r':rest)      -> splitLines rest
                ('\n':rest)      -> splitLines rest
                _                -> []
isLineTerminator c = c == '\r' || c == '\n'

• break函数把一个列表分成两部分，它的第一个参数是一个函数，这个函数必须去检查列表中的元素，并且返回一个Bool值来表示列表是否在那个元素处被分开
• break函数返回一个二元组，凭借一个谓词（即一个返回Bool值的函数）判断是否返回第一个True之前的元素构成的列表（前缀）和剩下的元素构成的列表（后缀）

行终止符转换程序

Windows系统与类Unix系统的读、写文件操作是不同的。Windows系统用文本模式读取一个文件的时候，文件I/O库把行终止序列“\r\n”（回车后跟着换行）转换成“\n”（单个换行），写一个文件的时候，文件I/O库会做相反的事情；而类Unix系统上，文本模式读写不做任何的转换工作。

以lines函数为例，由于它仅仅在换行符处分离文本，会留下回车跟在行的结尾处，如果在Linux或Unix上读取一个Windows生成的文本文件，会在每一行的结尾处得到尾随的回车；如果在Windows系统上读取一个在类Unix系统上写入的文件，行终止符会变得很乱。这使得行终止符转换程序具有现实意义。

--file fixLines.hs
import System.Environment (getArgs)

isLineTerminator c = c == '\r' || c == '\n'

splitLines [] = []
splitLines cs =
    let (pre, suf) = break isLineTerminator cs
    in  pre : case suf of
                ('\r':'\n':rest) -> splitLines rest
                ('\r':rest)      -> splitLines rest
                ('\n':rest)      -> splitLines rest
                _                -> []

fixLines inputStr = unlines (splitLines inputStr)

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

main = mainWith myFunction
  where mainWith function = do
          args <- getArgs
          case args of
            [inputFile,outputFile] -> interactWith function inputFile outputFile
            _ -> putStrLn "error: exactly two arguments needed"
        myFunction = fixLines

• lines函数 在行边界上分离一段文本字符串，返回一个忽略了行终止字符的字符串列表
• unlines函数 将由字符串组成的列表串联起来，并且在每个字符串元素的末尾加上换行符
• words函数 利用任何空格符分割字符串
• unwords函数 利用一个空格符把由字符串构成的列表连接起来

中缀函数

如果一个函数或构造器带两个或更多的参数，可以选择使用中缀形式，用中缀表示法定义或应用一个函数或值构造器，需用反引号包围它的名称

--中缀函数
a `plus` b = a + b
--中缀值构造器
data a `Pair` b = a `Pair` b
                  deriving (Show)
-- we can use the constructor either prefix or infix
foo = Pair 1 2
bar = True `Pair` "quux"

练习

--file myfunc.hs
--写一些安全的列表函数
safeHead::[a]->Maybe a
safeHead []=Nothing
safeHead (x:xs)=Just x

safeTail::[a]->Maybe [a]
safeTail []=Nothing
safeTail (x:xs)=Just xs

--写一个和words功能近似的函数splitWith函数
--输入一个谓词和一个任意类型元素组成的列表
--在使谓词返回False的元素处分割这个列表
splitWith::(a->Bool)->[a]->[[a]]
splitWith func xs=
  let (pre,suf)=span func xs
  in pre : case suf of
             (x:rest)->splitWith func rest
             _->[]

--file firstWord.hs
--利用命令行框架，编写一个打印输入数据的每一行的第一个单词的程序
import System.Environment (getArgs)

getfst::String->String
getfst oneline=head (words oneline)

getAllfst::[String]->[String]
getAllfst (oneline:restlines)=(getfst oneline):(getAllfst restlines)
getAllfst _=[]

getOutputStr::String->String
getOutputStr inputStr=unlines (getAllfst (lines inputStr))

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

main = mainWith myFunction
  where mainWith function = do
          args <- getArgs
          case args of
            [inputFile,outputFile] -> interactWith function inputFile outputFile
            _ -> putStrLn "error: exactly two arguments needed"
        myFunction = getOutputStr

--file transpose.hs
--转置文本程序 把“hello\nworld\n”转换成“hw\neo\nlr\nll\nod\n”
import System.Environment (getArgs)

transform::[Char]->[[Char]]
transform (c:cs)=[c]:transform cs
transform _=[]

transpose func strs=zipWith (:) (head strs) (func (last strs))

getOutputStr inputStr=unlines (transpose transform (lines inputStr))

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

main = mainWith myFunction
  where mainWith function = do
          args <- getArgs
          case args of
            [inputFile,outputFile] -> interactWith function inputFile outputFile
            _ -> putStrLn "error: exactly two arguments needed"
        myFunction = getOutputStr

循环的表示 显式递归

-- file IntParse.hs
import Data.Char (digitToInt)-- 只载入 Data.Char 中的 digitToInt 函数

--尾递归函数：如果输入非空，函数在尾模式中递归地调用自身
--基本情形（base case）处理空列表
--递归情形（recursive case）处理非空列表，对头元素进行某种操作，对余下的其他元素递归地处理
loop :: Int -> String -> Int
loop acc [] = acc
loop acc (x:xs) = let acc' = acc * 10 + digitToInt x
                  in loop acc' xs
asInt :: String -> Int
asInt xs = loop 0 xs

{-
import Data.Char(digitToInt)

asInt::String->Int
asInt xs=loop 0 xs
  where loop acc xs=
          case xs of
            []->acc
            (x:xs_)->loop acc_ xs_
              where acc_=acc*10 + digitToInt x
-}

//对应C函数
int asint(char *str){
    int acc; // accumulate the partial result
    for (acc = 0; isdigit(*str); str++)
        acc = acc * 10 + (*str -'0');
    return acc;
}

上述代码展示了一个惯用的结构递归（structural recursion）法：通过研究列表的结构，分别处理空列表和非空列表两种状况；非递归情形（空列表）被称为基本情形（终止情形、归纳情形），当对函数进行递归调用时，计算最终会回到基本情形上。

对列表元素进行转换

以显式递归的方法为例

import Data.Char (toUpper)
upperCase :: String -> String
upperCase (x: xs) = toUpper x : upperCase xs
upperCase []      = []

square :: [Double] -> [Double]
square (x:xs) = x*x : square xs
square []     = []

列表映射 map

使用 map 重写的 square 和 upperCase 函数如下，

import Data.Char (toUpper)
upperCase2 xs = map toUpper xs

square2 xs = map squareOne xs
    where squareOne x = x * x

因为map 的抽象出现在 square 和 upperCase 函数，所以可以通过观察这两个函数，找出它们之间的共同点，然后实现自己的 map 函数。

-- file myMap.hs
myMap :: (a -> b) -> [a] -> [b]
myMap f (x:xs) = f x : myMap f xs
myMap _ [] = []

筛选列表元素 filter

筛选函数的递归情形比之前的 map 函数要复杂一些，它使用守卫对元素进行条件判断，只有符合条件的元素，才会被加入进结果列表里。

-- file oddList.hs
oddList :: [Int] -> [Int]
oddList (x:xs) | odd x     = x : oddList xs
               | otherwise = oddList xs
oddList []                 = []

filter的显式递归定义如下

--file myfilter.hs
myfilter :: (a -> Bool) -> [a] -> [a]
myfilter p [] = []
myfilter p (x:xs)
    | p x       = x : myfilter p xs
    | otherwise = myfilter p xs

处理集合并得出结果 reduce

reduce将集合缩减为一个值，这种递归计算是纯函数语言里表示 loop 最自然的方式，

-- file mySum.hs
mySum xs = helper 0 xs
    where helper acc (x:xs) = helper (acc + x) xs
          helper acc []     = acc

helper 函数就是一个reduce，它通过尾递归进行计算，acc 是累积器（accumulator）参数，记录了当前列表元素的总和。

折叠 foldl foldr

折叠函数对一个列表中的所有元素做某种处理，并且一边处理元素，一边更新累积器，最后在处理完整个列表之后，返回累积器的值

-- file fold.hs
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl step acc (x:xs) = foldl step (step acc x) xs
foldl _ acc []        = acc
--niceSum xs = foldl (+) 0 xs
--niceSum [1, 2, 3]
--    == foldl (+) 0                   (1:2:3:[])
--    == foldl (+) (0 + 1)             (2:3:[])
--    == foldl (+) ((0 + 1) + 2)       (3:[])
--    == foldl (+) (((0 + 1) + 2) + 3) []
--    == (((0 + 1) + 2) + 3)

foldr :: (b -> a -> a) -> a -> [b] -> a
foldr step acc (x:xs) = step x (foldr step acc xs)
foldr _ acc []        = acc
--niceSumFoldr xs = foldr (+) 0 xs
--niceSumFoldr [1, 2, 3]
--    == foldr (+) 0 (1:2:3:[])
--    == 1 +           foldr (+) 0 (2:3:[])
--    == 1 + (2 +      foldr (+) 0 (3:[]))
--    == 1 + (2 + (3 + foldr (+) 0 []))
--    == 1 + (2 + (3 + 0))

关于foldr如何工作的直觉性解释是它用zero初始值替代了空列表，并且调用step函数替代列表的每个值构造器。实际上则应将它看成是对输入列表的一种转换，它的第一个参数决定了该怎么处理列表的 head 和 tail 部分；而它的第二个参数则决定了，当遇到空列表时，该用什么值来代替这个空列表

foldr的作用

所有可以用 foldr 定义的函数，统称为主递归（primitive recursive）

--file mfr.hs
--通过foldr定义filter
foldrFilter func xs=foldr step [] xs
  where step x acc | func x = x:acc
                  | otherwise =acc

--通过foldr定义map
foldrMap func xs=foldr step [] xs
  where step x acc=(func x):acc

--通过foldr定义foldl
foldrFoldl::(a->b->a)->a->[b]->a
foldrFoldl fstep acc xs=foldr step id xs acc
  where step x g a=g (fstep a x)
-- xs@(x:xs') and xs'@(x':xs'') and ...
-- foldr step id xs acc
-- ==step x (foldr step id xs') acc                   
--   -> ( foldr step id xs'                                 ) (fstep acc x)
-- ==step x (step x' (foldr step id xs'')) acc        
--   -> ( (foldr step id xs'')                  (fstep _ x')) (fstep acc x)
-- ==step x (step x' (step x'' (foldr step id xs''')))
--   -> ( ((foldr step id xs''')(fstep _' x'')) (fstep _ x')) (fstep acc x)
-- ...because foldr _ id []=id, let xs'''=[]
--   -> ( ( id                  (fstep _' x'')) (fstep _ x')) (fstep acc x)            

--通过foldr定义恒等identity转换
identity :: [a] -> [a]
identity xs = foldr (:) [] xs

--通过foldr定义++
append :: [a] -> [a] -> [a]
append xs ys = foldr (:) ys xs

匿名函数

Haskell的匿名函数以反斜杠符号 \ 为开始，后跟函数的参数（可以包含模式），函数体定义在 -> 符号之后。因为匿名函数从 lambda 演算而来，所以匿名函数通常也被称为 lambda 函数。lambda 函数的定义只能有一条语句，这种局限性，限制了在 lambda 定义中可使用的模式，也就是说，lambda函数只能表示一种情形，所以要注意别将函数应用到错误的模式。

unsafeHead = \(x:_) -> x
--unsafeHead [] 导致 *** Exception: unsafeHead.hs:2:14-24: Non-exhaustive patterns in lambda

部分函数应用和柯里化

在 Haskell 中，所有函数都只接受一个参数。所谓的多参函数，实际上是接受一个参数并返回另一个函数，这个被返回的函数也接受一个参数，最后返回值。柯里化即函数的部分应用（partial application of the function）指 函数正被它的其中几个参数（传入参数的数量，少于函数所能接受参数的数量）所应用。

节 Section

使用括号包围一个中序操作符，通过在括号里面提供左操作对象或者右操作对象，产生一个部分应用函数，这样的函数应用方式被称为节。

isInAlphabet = (`elem` ['A','a',...,'Z','z'])
--isInAlphabet 'f'==True 

As-模式

As-模式 形如xs@(:xs')，如果输入值能匹配 @ 符号右边的模式 (:xs') ，那么就将这个值绑定到 @ 符号左边的变量xs中

通过组合函数复用代码

--写一个行为和 Data.List.tails 类似，但是并不包含空列表后缀的函数
--tails "foo"==["foo","oo","o",""]
--利用As-模式
suffixes :: [a] -> [[a]]
suffixes xs@(_:xs') = xs : suffixes xs'
suffixes [] = []

--利用组合函数
import Data.List (tails)
suffixes2 xs = init (tails xs)

提取组合模式形成函数后再次定义

--组合模式
compose :: (b -> c) -> (a -> b) -> a -> c
compose f g x = f (g x)
--定义函数 
suffixes3 xs = compose init tails xs
--柯里化
suffixes4 = compose init tails

Prelude 里面，使用 (.) 操作符就可以起到与compose一样的组合起两个函数的作用。通过使用 (.) 来组合函数，并产生新函数，组合链的长度没有限制，只要 (.) 符号右边函数的输出值类型适用于 (.) 符号左边函数的输入值类型。

let capCount = length . filter (isUpper . head) . words
-- capCount "Hello there, Mon!"==2

严格求值

seq 函数对传入的第一个参数强迫（force）求值，然后返回它的第二个参数。
seq 的用法：

• 表达式中被求值的第一个必须是 seq
• 对多值严格求值时，可以连接起 seq 调用
• seq需要在运行时检查输入值是否已经被求值