所谓高阶函数，就是将函数对象作为函数的参数或者函数的返回值，高阶函数是抽象必不可少的工具

柯里化和部分函数

函数其实只接受一个参数

如果我说：Haskell 中，函数本质上只接受一个参数。你肯定会问：多参数函数怎么办呢？这时候高阶函数就出场了！

对于多参数函数，接受一个参数后，会返回一个接受剩余参数的函数，这就是柯里化。

比如常见的 max 函数，其类型

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

相当于，接受一个参数，返回另外一个接受一个参数的函数

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

ghci> max 4 5
5

相当于

ghci> (max 4) 5
5

代码中 (max 4) 生成了一个接受一个参数的部分函数。

部分参数生成部分函数

我们如果用部分参数调用函数，就会得到一个部分函数，所谓部分函数，就是指这个函数可以接受剩余的参数

注意：已经接受的参数作为状态被保存在了返回的部分函数中

--定义一个接收三个参数的函数
multThree :: (Num a) => a -> a -> a -> a
multThree x y z = x * y * z

--传入一个参数，返回一个接收两个参数的函数
ghci> let multTwoWithNine = multThree 9
ghci> multTwoWithNine 2 3
54

--继续传入一个参数，返回一个接受一个参数的函数
ghci> let multWithEighteen = multTwoWithNine 2
ghci> multWithEighteen 10
180

消除等号两边相同的变量可以得到部分函数

比如要定义一个和 100 比较大小的函数，传统方式是这样：

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

注意到定义两边都有变量 x，就像数学中等式变换一样，可以将等号两边的 x 消除，这样就得到了一个部分函数。

这个函数和上面函数的类型是完全相同的

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

中缀函数生成部分函数

中缀函数生成部分函数需要用括号括起来，比如

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

调用 divideByTen 200 就是 (/10) 200，和 200 / 10 等价。

参数的位置

因为 Haskell 是静态类型的，因此参数的位置一般都是很明确的，不需要考虑太多

比如，检查字符是否为大写的函数可以简化为

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

- 是个例外

这里减号 - 是个例外，因为他和负号相同，因此需要使用函数名 subtract

柯里化生成的部分函数不是 Show 的成员

和普通函数不同，通过部分调用生成的部分函数不能在交互式环境中显示，因为他不是 Show 的成员

高阶函数

首先看看以函数作为参数的高阶函数，比如接受一个函数作为参数并调用它两次

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

注意看它的类型声明，第一个参数是一个函数类型

因为柯里化可以非常容易的创建函数，因此部分函数和高阶函数很容易结合使用，非常强大

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 函数

前面我们用过 zip 函数，其将两个列表中的元素组合为序对。

下面我们来实现一个 zipWith 高阶函数，他也是将两个列表中的元素经过一定的处理后，合并成一个列表，但处理方法是作为参数传进去的

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]  
--任意一个列表为空则返回空
zipWith' _ [] _ = []  
zipWith' _ _ [] = []  

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

zipWith 结合部分函数，传入不同的处理函数，可以玩出很多花样

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 函数

flip 函数接受一个函数作参数，并回传一个相似的函数，只是将两个参数的顺序倒了个

下面的代码就是将这个问题描述了一遍：

• 定义了一个 g 函数，其返回值就是用颠倒的顺序调用 f 函数
• 最后将 g 函数返回

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

数学等式又来了：消除中间变量 g 函数，可以进一步简化代码

再加上参数定义，这个函数就可以直接使用了

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

调用一下

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 函数就是列表变换

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

map 函数有非常多的用法

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 函数，过滤列表

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 的功能也可以用列表解析实现，特别是多条件过滤的情况下，用 filter 就比较啰嗦了

之前的快速排序使用列表解析进行过滤的，这里把他改成用 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 函数

从一个列表中取出符合条件的项，组成一个新列表。比如“找出所有小于 10000 且为奇数的平方数的和”

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

当然，也可以用列表解析实现

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

Collatz 串行

算法：

• 取一个自然数，若为偶数就除以 2
  ；若为奇数就乘以 3 再加 1
• 再用相同的方式处理所得的结果，循环得到一组数字构成的的链
• 无论任何以任何数字开始，最终的结果都会归 1

问题：以 1 到 100 之间的所有数作为起始数，会有多少个链的长度大于 15?

下面是生成链串的函数

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

调用效果如下

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]

下面是过滤函数

--生成一个列表，里面的项都是长度大于 15 的串链
numLongChains :: Int  
numLongChains = length (filter isLong (map chain [1..100]))  
    where isLong xs = length xs > 15

map 的其他用法

一般情况下使用 map ，列表中的项作为参数，正好符合处理函数需要，处理后的数据组成了新的列表，比如

map (*2) [0..]

有的时候，仅仅列表中的项作为参数，比处理函数需要的参数数目要少，这样得到的就不是转换后数据的列表，而是部分函数的列表。比如： map (*) [0..] 得到的结果为 [(0*),(1*),(2*)..]

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

lambda

lambda 就是匿名函数，可以省略函数名称的定义，例如前面过滤 Collatz 串的函数，其中的过滤条件函数可以用匿名函数替代

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

用部分函数代替匿名函数

看看下面的代码，等式两边都有变量 x，我们自然而然想到了柯里化。

大部分用到匿名函数的地方都可以用部分函数代替，代码更简洁

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

//替换成

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

参数相关问题

匿名函数也可以有多个参数

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]

结合柯里化和匿名函数理解函数的定义

1. 函数的定义本质上可以看做是给一个匿名函数对象起一个名字
2. 由于柯里化，匿名函数也可以看做是只接受一个参数的函数

下面两段代码是等价的

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

利用匿名函数让 flip 函数根据可读性

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

折叠

折叠函数接受三个参数

• 一个归约函数，接受两个参数：归约值和列表的当前项
• 归约初值
• 一个列表

lfold 函数：左折叠

用左折叠函数定义一个求和函数

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

注意：左折叠的规约函数的参数顺序是：归约值，列表的当前项

前面说过，大部分匿名函数都可以用部分函数代替，改写代码如下，非常的简洁

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

再用左折叠实现一个 elem 函数，这里想演示的是，初值怎么选取

注意：这里的实现效率不高，因为他在找到了目标元素后，仍然继续遍历后面的元素

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

rfold 函数：右折叠

右折叠和左折叠类似，归约函数的参数顺序和左折叠相反

用右折叠实现一个 map 函数

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

用左折叠也能实现 map 函数，但是得使用 ++ 连接符，性能较差，因此生成新 List 的时候人们一般都是使用右折叠。

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

左折叠和右折叠最大的区别

• 右折叠可以处理无限长度的数据结构，而左折叠不可以
• 将无限 List 从中断开执行左折叠是可以的，不过若是向右，就永远到不了头了

foldl1 与 foldr1

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

注意：这里 foldl1 和 foldr1 折叠的 List 中至少要有一个元素，若使用空 List 就会产生一个运行时错误

为了体会 fold 的威力，我们就用它实现几个库函数：

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 相似，只是它们会记录下累加值的所有状态到一个 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]]

优先级提升符号 $

$ 符号相当于为其后的表达式加了一个括号，改变优先级，例如

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]

此外，用 $ 符号修饰的数据可以调用函数，这个功能在 map 中常用

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

组合函数

组合函数和数学上的组合函数类似，将几个函数合成一个函数，定义如下

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

有了组合函数，部分使用匿名函数的情况可以简化代码，例如：将列表中的数值全部转换成负数

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

改为使用组合函数

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]

多参数函数的组合

组合多参数函数时，需要使用括号或者美元符号

sum (replicate 5 (max 6.7 8.9))

可以重写为

(sum . replicate 5 . max 6.7) 8.9

或

sum . replicate 5 . max 6.7 $ 8.9

在最后一个参数之前加美元符号，在其他函数之间加点号，这里是另外一个例子；

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]

函数组合可以让柯里化更容易

下面的函数等号两边都有 x ，但是要想柯里化却不是很容易

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

使用函数组合后，就很容易柯里化了

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

不要炫代码

函数组合、部分函数非常酷，但是有时候会导致代码难以理解，因此尽量写让人容易理解的代码，比如之前“求了小于 10000 的所有奇数的平方的和”的例子

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

用函数组合修改为如下代码，一般人不容易理解

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