所謂高階函數(shù)庶弃，就是將函數(shù)對象作為函數(shù)的參數(shù)或者函數(shù)的返回值蝎困，高階函數(shù)是抽象必不可少的工具

柯里化和部分函數(shù)

函數(shù)其實(shí)只接受一個參數(shù)

如果我說：Haskell 中仲义，函數(shù)本質(zhì)上只接受一個參數(shù)。你肯定會問：多參數(shù)函數(shù)怎么辦呢氏身？這時候高階函數(shù)就出場了寒屯！

對于多參數(shù)函數(shù)荐捻，接受一個參數(shù)后，會返回一個接受剩余參數(shù)的函數(shù)寡夹，這就是柯里化处面。

比如常見的 max 函數(shù)，其類型

max :: (Ord a) => a -> a -> a

相當(dāng)于菩掏，接受一個參數(shù)魂角，返回另外一個接受一個參數(shù)的函數(shù)

max :: (Ord a) => a -> (a -> a)

ghci> max 4 5
5

相當(dāng)于

ghci> (max 4) 5
5

代碼中 (max 4) 生成了一個接受一個參數(shù)的部分函數(shù)。

部分參數(shù)生成部分函數(shù)

我們?nèi)绻貌糠謪?shù)調(diào)用函數(shù)智绸，就會得到一個部分函數(shù)野揪，所謂部分函數(shù)，就是指這個函數(shù)可以接受剩余的參數(shù)

注意：已經(jīng)接受的參數(shù)作為狀態(tài)被保存在了返回的部分函數(shù)中

--定義一個接收三個參數(shù)的函數(shù)
multThree :: (Num a) => a -> a -> a -> a
multThree x y z = x * y * z

--傳入一個參數(shù)瞧栗，返回一個接收兩個參數(shù)的函數(shù)
ghci> let multTwoWithNine = multThree 9
ghci> multTwoWithNine 2 3
54

--繼續(xù)傳入一個參數(shù)斯稳，返回一個接受一個參數(shù)的函數(shù)
ghci> let multWithEighteen = multTwoWithNine 2
ghci> multWithEighteen 10
180

消除等號兩邊相同的變量可以得到部分函數(shù)

比如要定義一個和 100 比較大小的函數(shù)，傳統(tǒng)方式是這樣：

compareWithHundred :: (Num a, Ord a) => a -> Ordering
compareWithHundred x = compare 100 x

注意到定義兩邊都有變量 x迹恐，就像數(shù)學(xué)中等式變換一樣挣惰，可以將等號兩邊的 x 消除，這樣就得到了一個部分函數(shù)殴边。

這個函數(shù)和上面函數(shù)的類型是完全相同的

compareWithHundred :: (Num a, Ord a) => a -> Ordering
compareWithHundred = compare 100

中綴函數(shù)生成部分函數(shù)

中綴函數(shù)生成部分函數(shù)需要用括號括起來通熄，比如

divideByTen :: (Floating a) => a -> a
divideByTen = (/10)

調(diào)用 divideByTen 200 就是 (/10) 200，和 200 / 10 等價找都。

參數(shù)的位置

因?yàn)?Haskell 是靜態(tài)類型的，因此參數(shù)的位置一般都是很明確的廊酣，不需要考慮太多

比如能耻，檢查字符是否為大寫的函數(shù)可以簡化為

isUpperAlphanum :: Char -> Bool
isUpperAlphanum = (`elem` ['A'..'Z'])

- 是個例外

這里減號 - 是個例外，因?yàn)樗拓?fù)號相同，因此需要使用函數(shù)名 subtract

柯里化生成的部分函數(shù)不是 Show 的成員

和普通函數(shù)不同晓猛，通過部分調(diào)用生成的部分函數(shù)不能在交互式環(huán)境中顯示饿幅，因?yàn)樗皇?Show 的成員

高階函數(shù)

首先看看以函數(shù)作為參數(shù)的高階函數(shù)，比如接受一個函數(shù)作為參數(shù)并調(diào)用它兩次

applyTwice :: (a -> a) -> a -> a  
applyTwice f x = f (f x)

注意看它的類型聲明戒职，第一個參數(shù)是一個函數(shù)類型

因?yàn)榭吕锘梢苑浅Ｈ菀椎膭?chuàng)建函數(shù)栗恩，因此部分函數(shù)和高階函數(shù)很容易結(jié)合使用，非常強(qiáng)大

ghci> applyTwice (+3) 10  
16  

ghci> applyTwice (++ " HAHA") "HEY"  
"HEY HAHA HAHA"  

ghci> applyTwice ("HAHA " ++) "HEY"  
"HAHA HAHA HEY"  

ghci> applyTwice (multThree 2 2) 9  
144  

ghci> applyTwice (3:) [1]  
[3,3,1]

zipWith 函數(shù)

前面我們用過 zip 函數(shù)洪燥，其將兩個列表中的元素組合為序?qū)Α?/p>

下面我們來實(shí)現(xiàn)一個 zipWith 高階函數(shù)磕秤，他也是將兩個列表中的元素經(jīng)過一定的處理后，合并成一個列表捧韵，但處理方法是作為參數(shù)傳進(jìn)去的

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]  
--任意一個列表為空則返回空
zipWith' _ [] _ = []  
zipWith' _ _ [] = []  

zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

zipWith 結(jié)合部分函數(shù)市咆，傳入不同的處理函數(shù)，可以玩出很多花樣

ghci> zipWith' (+) [4,2,5,6] [2,6,2,3]  
[6,8,7,9]  

ghci> zipWith' max [6,3,2,1] [7,3,1,5]  
[7,3,2,5]  

ghci> zipWith' (++) ["foo "再来，"bar "蒙兰，"baz "] ["fighters"，"hoppers"芒篷，"aldrin"]  
["foo fighters","bar hoppers","baz aldrin"] 

ghci> zipWith' (*) (replicate 5 2) [1..]  
[2,4,6,8,10]  

ghci> zipWith' (zipWith' (*)) [[1,2,3],[3,5,6],[2,3,4]] [[3,2,2],[3,4,5],[5,4,3]]  
[[3,4,6],[9,20,30],[10,12,12]]

flip 函數(shù)

flip 函數(shù)接受一個函數(shù)作參數(shù)搜变，并回傳一個相似的函數(shù)，只是將兩個參數(shù)的順序倒了個

下面的代碼就是將這個問題描述了一遍：

• 定義了一個 g 函數(shù)针炉，其返回值就是用顛倒的順序調(diào)用 f 函數(shù)
• 最后將 g 函數(shù)返回

flip' :: (a -> b -> c) -> (b -> a -> c)  
flip' f = g  
    where g x y = f y x

數(shù)學(xué)等式又來了：消除中間變量 g 函數(shù)挠他，可以進(jìn)一步簡化代碼

再加上參數(shù)定義，這個函數(shù)就可以直接使用了

flip' :: (a -> b -> c) -> b -> a -> c  
flip' f y x = f x y

調(diào)用一下

ghci> flip' zip [1,2,3,4,5] "hello"  
[('h',1),('e',2),('l',3),('l',4),('o',5)] 

ghci> zipWith (flip' div) [2,2..] [10,8,6,4,2]  
[5,4,3,2,1]

map 與 filter

map 函數(shù)就是列表變換

map :: (a -> b) -> [a] -> [b]  
map _ [] = []  
map f (x:xs) = f x : map f xs

map 函數(shù)有非常多的用法

ghci> map (+3) [1,5,3,1,6]  
[4,8,6,4,9]  

ghci> map (++ "!") ["BIFF"糊识，"BANG"绩社，"POW"]  
["BIFF!","BANG!","POW!"]  

ghci> map (replicate 3) [3..6]  
[[3,3,3],[4,4,4],[5,5,5],[6,6,6]]  

ghci> map (map (^2)) [[1,2],[3,4,5,6],[7,8]]  
[[1,4],[9,16,25,36],[49,64]]  

ghci> map fst [(1,2),(3,5),(6,3),(2,6),(2,5)]  
[1,3,6,2,2]

map 的大部分用法都可以用列表解析來代替

filter 函數(shù)，過濾列表

filter :: (a -> Bool) -> [a] -> [a]  
filter _ [] = []  
filter p (x:xs)   
    | p x       = x : filter p xs  
    | otherwise = filter p xs

使用方法

ghci> filter (>3) [1,5,3,2,1,6,4,3,2,1]  
[5,6,4]  

ghci> filter (==3) [1,2,3,4,5]  
[3]  

ghci> filter even [1..10]  
[2,4,6,8,10]  

ghci> let notNull x = not (null x) in filter notNull [[1,2,3],[],[3,4,5],[2,2],[],[],[]]  
[[1,2,3],[3,4,5],[2,2]]  

ghci> filter (`elem` ['a'..'z']) "u LaUgH aT mE BeCaUsE I aM diFfeRent"  
"uagameasadifeent" 

ghci> filter (`elem` ['A'..'Z']) "i lauGh At You BecAuse u r aLL the Same"  
"GAYBALLS"

注意：filter 的功能也可以用列表解析實(shí)現(xiàn)赂苗，特別是多條件過濾的情況下愉耙，用 filter 就比較啰嗦了

之前的快速排序使用列表解析進(jìn)行過濾的，這里把他改成用 filter 過濾拌滋，代碼如下

quicksort :: (Ord a) => [a] -> [a]    
quicksort [] = []    
quicksort (x:xs) =     
    let smallerSorted = quicksort (filter (<=x) xs)
        biggerSorted = quicksort (filter (>x) xs)   
    in  smallerSorted ++ [x] ++ biggerSorted

takeWhile 函數(shù)

從一個列表中取出符合條件的項(xiàng)朴沿，組成一個新列表。比如“找出所有小于 10000 且為奇數(shù)的平方數(shù)的和”

ghci> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))  
166650

當(dāng)然败砂，也可以用列表解析實(shí)現(xiàn)

ghci> sum (takeWhile (<10000) [m | m <- [n^2 | n <- [1..]], odd m])  
166650

Collatz 串行

算法：

• 取一個自然數(shù)赌渣，若為偶數(shù)就除以 2
  ；若為奇數(shù)就乘以 3 再加 1
• 再用相同的方式處理所得的結(jié)果昌犹，循環(huán)得到一組數(shù)字構(gòu)成的的鏈
• 無論任何以任何數(shù)字開始坚芜，最終的結(jié)果都會歸 1

問題：以 1 到 100 之間的所有數(shù)作為起始數(shù)，會有多少個鏈的長度大于 15?

下面是生成鏈串的函數(shù)

--生成鏈串的函數(shù)
chain :: (Integral a) => a -> [a]  
chain 1 = [1]  
chain n  
    | even n =  n:chain (n `div` 2)  
    | odd n  =  n:chain (n*3 + 1)

調(diào)用效果如下

ghci> chain 10  
[10,5,16,8,4,2,1]  

ghci> chain 1  
[1]  

ghci> chain 30  
[30,15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]

下面是過濾函數(shù)

--生成一個列表斜姥，里面的項(xiàng)都是長度大于 15 的串鏈
numLongChains :: Int  
numLongChains = length (filter isLong (map chain [1..100]))  
    where isLong xs = length xs > 15

map 的其他用法

一般情況下使用 map 鸿竖，列表中的項(xiàng)作為參數(shù)沧竟，正好符合處理函數(shù)需要，處理后的數(shù)據(jù)組成了新的列表缚忧，比如

map (*2) [0..]

有的時候悟泵，僅僅列表中的項(xiàng)作為參數(shù)，比處理函數(shù)需要的參數(shù)數(shù)目要少闪水，這樣得到的就不是轉(zhuǎn)換后數(shù)據(jù)的列表糕非，而是部分函數(shù)的列表。比如： map (*) [0..] 得到的結(jié)果為 [(0*),(1*),(2*)..]

ghci> let listOfFuns = map (*) [0..]  
ghci> (listOfFuns !! 4) 5  
20

lambda

lambda 就是匿名函數(shù)球榆，可以省略函數(shù)名稱的定義朽肥，例如前面過濾 Collatz 串的函數(shù)，其中的過濾條件函數(shù)可以用匿名函數(shù)替代

numLongChains :: Int  
numLongChains = length (filter (\xs -> length xs > 15) (map chain [1..100]))

用部分函數(shù)代替匿名函數(shù)

看看下面的代碼芜果，等式兩邊都有變量 x鞠呈，我們自然而然想到了柯里化。

大部分用到匿名函數(shù)的地方都可以用部分函數(shù)代替右钾，代碼更簡潔

map (\x -> x+3) [1,6,3,2]

//替換成

map (+3) [1,6,3,2]

參數(shù)相關(guān)問題

匿名函數(shù)也可以有多個參數(shù)

ghci> zipWith (\a b -> (a * 30 + 3) / b) [5,4,3,2,1] [1,2,3,4,5]  
[153.0,61.5,31.0,15.75,6.6]

也可以使用模式匹配蚁吝，但是無法使用多種模式

ghci> map (\(a,b) -> a + b) [(1,2),(3,5),(6,3),(2,6),(2,5)]  
[3,8,9,8,7]

結(jié)合柯里化和匿名函數(shù)理解函數(shù)的定義

1. 函數(shù)的定義本質(zhì)上可以看做是給一個匿名函數(shù)對象起一個名字
2. 由于柯里化，匿名函數(shù)也可以看做是只接受一個參數(shù)的函數(shù)

下面兩段代碼是等價的

addThree :: (Num a) => a -> a -> a -> a  
addThree x y z = x + y + z

addThree :: (Num a) => a -> a -> a -> a  
addThree = \x -> \y -> \z -> x + y + z

利用匿名函數(shù)讓 flip 函數(shù)根據(jù)可讀性

flip' :: (a -> b -> c) -> b -> a -> c  
flip' f = \x y -> f y x

折疊

折疊函數(shù)接受三個參數(shù)

• 一個歸約函數(shù)舀射，接受兩個參數(shù)：歸約值和列表的當(dāng)前項(xiàng)
• 歸約初值
• 一個列表

lfold 函數(shù)：左折疊

用左折疊函數(shù)定義一個求和函數(shù)

sum' :: (Num a) => [a] -> a  
sum' xs = foldl (\acc x -> acc + x) 0 xs

注意：左折疊的規(guī)約函數(shù)的參數(shù)順序是：歸約值窘茁，列表的當(dāng)前項(xiàng)

前面說過，大部分匿名函數(shù)都可以用部分函數(shù)代替脆烟，改寫代碼如下山林，非常的簡潔

sum' :: (Num a) => [a] -> a  
sum' = foldl (+) 0

再用左折疊實(shí)現(xiàn)一個 elem 函數(shù)，這里想演示的是邢羔，初值怎么選取

注意：這里的實(shí)現(xiàn)效率不高驼抹，因?yàn)樗谡业搅四繕?biāo)元素后，仍然繼續(xù)遍歷后面的元素

elem' :: (Eq a) => a -> [a] -> Bool  
elem' y ys = foldl (\acc x -> if x == y then True else acc) False ys

rfold 函數(shù)：右折疊

右折疊和左折疊類似拜鹤，歸約函數(shù)的參數(shù)順序和左折疊相反

用右折疊實(shí)現(xiàn)一個 map 函數(shù)

map' :: (a -> b) -> [a] -> [b]  
map' f xs = foldr (\x acc -> f x : acc) [] xs

用左折疊也能實(shí)現(xiàn) map 函數(shù)框冀，但是得使用 ++ 連接符，性能較差敏簿，因此生成新 List 的時候人們一般都是使用右折疊明也。

map' f xs = foldl (\acc x -> acc ++ [f x]) [] xs

左折疊和右折疊最大的區(qū)別

• 右折疊可以處理無限長度的數(shù)據(jù)結(jié)構(gòu)，而左折疊不可以
• 將無限 List 從中斷開執(zhí)行左折疊是可以的惯裕，不過若是向右温数，就永遠(yuǎn)到不了頭了

foldl1 與 foldr1

與 foldl 和 foldr 相似，只是他們假定 List 的首(或尾)元素作為起始值

注意：這里 foldl1 和 foldr1 折疊的 List 中至少要有一個元素蜻势，若使用空 List 就會產(chǎn)生一個運(yùn)行時錯誤

為了體會 fold 的威力撑刺，我們就用它實(shí)現(xiàn)幾個庫函數(shù)：

maximum' :: (Ord a) => [a] -> a  
maximum' = foldr1 (\x acc -> if x > acc then x else acc)  

reverse' :: [a] -> [a]  
reverse' = foldl (\acc x -> x : acc) []  

product' :: (Num a) => [a] -> a  
product' = foldr1 (*)  

filter' :: (a -> Bool) -> [a] -> [a]  
filter' p = foldr (\x acc -> if p x then x : acc else acc) []  

head' :: [a] -> a  
head' = foldr1 (\x _ -> x)  

last' :: [a] -> a  
last' = foldl1 (\_ x -> x)

scanl 和 scanr

與 foldl 和 foldr 相似，只是它們會記錄下累加值的所有狀態(tài)到一個 List握玛。也有 scanl1 和 scanr1

ghci> scanl (+) 0 [3,5,2,1]  
[0,3,8,10,11] 

ghci> scanr (+) 0 [3,5,2,1]  
[11,8,3,1,0]  

ghci> scanl1 (\acc x -> if x > acc then x else acc) [3,4,5,3,7,9,2,1]  
[3,4,5,5,7,9,9,9]  

ghci> scanl (flip (:)) [] [3,2,1]  
[[],[3],[2,3],[1,2,3]]

優(yōu)先級提升符號 $

$ 符號相當(dāng)于為其后的表達(dá)式加了一個括號猜煮，改變優(yōu)先級次员，例如

sum (map sqrt [1..130])
sum $ map sqrt [1..130]

sqrt (3+4+9)
sqrt $ 3+4+9

f (g (z x)) 
f $ g $ z x 

sum (filter (> 10) (map (*2) [2..10])  
sum $ filter (> 10) $ map (*2) [2..10]

此外，用 $ 符號修飾的數(shù)據(jù)可以調(diào)用函數(shù)王带，這個功能在 map 中常用

ghci> map ($ 3) [(4+),(10*),(^2),sqrt]  
[7.0,30.0,9.0,1.7320508075688772]

組合函數(shù)

組合函數(shù)和數(shù)學(xué)上的組合函數(shù)類似，將幾個函數(shù)合成一個函數(shù)市殷，定義如下

(.) :: (b -> c) -> (a -> b) -> a -> c  
f . g = \x -> f (g x)

有了組合函數(shù)愕撰，部分使用匿名函數(shù)的情況可以簡化代碼，例如：將列表中的數(shù)值全部轉(zhuǎn)換成負(fù)數(shù)

ghci> map (\x -> negate (abs x)) [5,-3,-6,7,-3,2,-19,24]  
[-5,-3,-6,-7,-3,-2,-19,-24]

改為使用組合函數(shù)

ghci> map (negate . abs) [5,-3,-6,7,-3,2,-19,24]  
[-5,-3,-6,-7,-3,-2,-19,-24]

再比如

ghci> map (\xs -> negate (sum (tail xs))) [[1..5],[3..6],[1..7]]  
[-14,-15,-27]

可以改為：

ghci> map (negate . sum . tail) [[1..5],[3..6],[1..7]]  
[-14,-15,-27]

多參數(shù)函數(shù)的組合

組合多參數(shù)函數(shù)時醋寝，需要使用括號或者美元符號

sum (replicate 5 (max 6.7 8.9))

可以重寫為

(sum . replicate 5 . max 6.7) 8.9

或

sum . replicate 5 . max 6.7 $ 8.9

在最后一個參數(shù)之前加美元符號搞挣，在其他函數(shù)之間加點(diǎn)號，這里是另外一個例子音羞；

replicate 100 (product (map (*3) (zipWith max [1,2,3,4,5] [4,5,6,7,8])))

可以改為

replicate 100 . product . map (*3) . zipWith max [1,2,3,4,5] $ [4,5,6,7,8]

函數(shù)組合可以讓柯里化更容易

下面的函數(shù)等號兩邊都有 x 囱桨，但是要想柯里化卻不是很容易

fn x = ceiling (negate (tan (cos (max 50 x))))

使用函數(shù)組合后，就很容易柯里化了

fn = ceiling . negate . tan . cos . max 50

不要炫代碼

函數(shù)組合嗅绰、部分函數(shù)非成岢Γ酷，但是有時候會導(dǎo)致代碼難以理解窘面，因此盡量寫讓人容易理解的代碼翠语，比如之前“求了小于 10000 的所有奇數(shù)的平方的和”的例子

oddSquareSum :: Integer  
oddSquareSum = sum (takeWhile (<10000) (filter odd (map (^2) [1..])))

用函數(shù)組合修改為如下代碼，一般人不容易理解

oddSquareSum :: Integer  
oddSquareSum = sum . takeWhile (<10000) . filter odd . map (^2) $ [1..]

若是給別人看财边，我可能就這么寫了：

oddSquareSum :: Integer  
oddSquareSum =   
    let oddSquares = filter odd $ map (^2) [1..]  
        belowLimit = takeWhile (<10000) oddSquares  
    in  sum belowLimit