Haskell 基本语法（四）高阶函数

Haskell 中的函数可以作为另一个函数的参数或返回值，这类函数叫做高阶函数（high order functions）。
想要通过定义是什么而不是定义一系列可以改变程序状态的步骤来完成计算过程，高阶函数是必不可少的。

Curried functions

Haskell 中的函数实际上都只接收一个参数。前面遇到的接收多个参数的函数是一种 Curried functions，可以看作某种特殊形式。
比如 max 4 5，看上去是向函数 max 传入两个参数 4 和 5，返回数值较大的 5。实际的计算过程是 (max 4) 5。

Prelude> max 4 5
5
Prelude> (max 4) 5
5

首先将参数 4 传递给函数 max，会返回另一个函数，该函数接收任意一个参数，将该参数与数字 4 比较，返回较大的数。所以后面将 5 传给函数 (max 4) 后，得到最终的结果 5。

Prelude> let maxWithFour = max 4
Prelude> maxWithFour 5
5

那么这种形式的函数究竟有什么好处呢？

当我们使用部分参数调用某个函数的时候，并不会直接得到结果，而是返回一个部分应用（partially applied）的函数。这个部分应用的函数可以继续接收剩余的参数，最终得到计算结果。

partially applied 机制可以方便我们简单地实现动态地创建函数、将函数作为参数传入、用特定数据初始化函数等需求。

对于函数 multThree：
let multThree x y z = x * y * z
它可以接收三个数字作为参数，并计算这三个参数的乘积作为返回值。

如 multThree 3 5 9，实际上的执行流程为 ((multThree 3) 5) 9。

• 将数字 3 传递给 multThree，它会返回一个函数 (multThree 3)。该函数接收任意两个数字，并计算它们和 3 的乘积
• 将数字 5 传递给 (multThree 3)，返回另一个函数 ((multThree 3) 5)。该函数接收任意一个数字，并计算它和 15 的乘积
• 将数字 9 传递给 ((multThree 3) 5)，返回 9 和 15 的乘积作为结果

Prelude> let multThreeNums x y z = x * y * z
Prelude> multThreeNums 2 3 4
24
Prelude> let multTwoNumsWithNine = multThreeNums 9
Prelude> multTwoNumsWithNine 2 3
54
Prelude> let multOneNumWithEighteen = multTwoNumsWithNine 2
Prelude> multOneNumWithEighteen 10
180

中缀函数如 + - * / 等也可以 partially applied。

比如可以将数字 5 传递给中缀函数 + 生成一个新的函数 (5+)，而新函数 (5+) 可以接收一个数字作为参数，返回该参数与 5 的和。
即函数 (5+) 其实是中缀函数 + 固定一个参数 5 之后生成的新函数，这个新函数接收任何一个数字作为另一个加数并求和。

使用 / 固定除数生成新函数 divideByTen：

Prelude> let divideByTen = (/10)
Prelude> divideByTen 200
20.0
Prelude> (/10) 200
20.0
Prelude> 200 / 10
20.0

divideByTen 200 等同于 (/10) 200 等同于 200 / 10。

同样的方式还可以定义 divideTen 固定被除数：

Prelude> let divideTen = (10/)
Prelude> divideTen 2
5.0
Prelude> (10/) 2
5.0
Prelude> 10 / 2
5.0

检查输入的字符是否是大写字母：

Prelude> let isUpperAlphanum = (`elem` ['A'..'Z'])
Prelude> isUpperAlphanum 'D'
True
Prelude> isUpperAlphanum 'a'
False

函数作为参数

Prelude> let applyTwice f x = f (f x)
Prelude> applyTwice (+3) 10
16
Prelude> applyTwice (++ " HAHA") "HEY"
"HEY HAHA HAHA"
Prelude> applyTwice ("HAHA " ++) "HEY"
"HAHA HAHA HEY"
Prelude> applyTwice (3:) [1]
[3,3,1]

zipWith 的自定义实现

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

Prelude> :{
Prelude| zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
ith' f Prelude| zipWith' _ [] _ = []
Prelude| zipWith' _ _ [] = []
Prelude| zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys
Prelude| :}
Prelude>
Prelude> zipWith' (+) [4,2,5,6] [2,6,2,3]
[6,8,7,9]
Prelude> zipWith' (++) ["foo ", "bar ", "baz "] ["fighters", "hoppers", "aldrin"]
["foo fighters","bar hoppers","baz aldrin"]
Prelude> zipWith' (*) (replicate 5 2) [1..]
[2,4,6,8,10]

flip 的自定义实现

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

Prelude> :{
Prelude| flip' :: (a -> b -> c) -> b -> a -> c
Prelude| flip' f y x = f x y
Prelude| :}
Prelude>
Prelude> flip' zip [1,2,3,4,5] "hello"
[('h',1),('e',2),('l',3),('l',4),('o',5)]
Prelude> zipWith (flip' div) [2,2..] [10,8,6,4,2]
[5,4,3,2,1]

Maps & Filters

map 接收一个函数和一个列表作为参数，可以将函数应用到列表的每一项元素上。

map 函数的定义如下：

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

Prelude> map (+3) [1,5,3,1,6]
[4,8,6,4,9]
Prelude> map (++ "!") ["BIFF", "BANG", "POW"]
["BIFF!","BANG!","POW!"]
Prelude> map (replicate 3) [3..6]
[[3,3,3],[4,4,4],[5,5,5],[6,6,6]]
Prelude> map (map (^2)) [[1,2],[3,4,5,6],[7,8]]
[[1,4],[9,16,25,36],[49,64]]
Prelude> map fst [(1,2),(3,5),(6,3),(2,6),(2,5)]
[1,3,6,2,2]

filter 接收一个判断函数和一个列表作为参数，返回列表中所有使判断函数为真的元素。

filter 函数的定义如下：

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

Prelude> filter (>3) [1,5,3,2,1,6,4,3,2,1]
[5,6,4]
Prelude> filter (==3) [1,2,3,4,5]
[3]
Prelude> filter even [1..10]
[2,4,6,8,10]
Prelude> 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]]
Prelude> filter (`elem` ['a'..'z']) "u LaUgH aT mE BeCaUsE I aM diFfeRent"
"uagameasadifeent"
Prelude> filter (`elem` ['A'..'Z']) "i lauGh At You BecAuse u r aLL the Same"
"GAYBALLS"

借助 filter 实现 quicksort：

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

找出 100000 以内能够被 3829 整除的最大的数：

largestDivisible :: (Integral a) => a
largestDivisible = head (filter p [100000,99999..])
    where p x = x `mod` 3829 == 0

其中 p x = x `mod` 3829 == 0 定义了函数 p 作为 filter 的判断函数，而列表 [100000, 99999..] 实际上是一个逆序的无穷列表。
借助 Haskell 的惰性计算机制，函数获取的是最大的可被整除的数，获得该值后就不会再继续计算下去。

实际上还可以这样使用 map 函数：
map (*) [0..]
将函数 * 映射到列表 [0..]，会返回一个包含一系列函数的新列表。新列表的形式类似 [(0*),(1*),(2*),(3*),(4*),(5*)..]。
其中的任何一个函数如 (4*)，都是接收两个参数的函数 * 固定了一个参数后的形式，再向其传入一个参数即可完成乘法运算。

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

!! 函数可以从指定列表中根据索引值获取特定的元素。(listOfFuns !! 4) 即为 (4*)。

Lambdas

Lambda 基本上是代码中只使用一次的匿名函数。
由 \ 反斜杠符号指定参数，-> 符号指定函数体。

Prelude> zipWith (\a b -> a * b - 1) [5,4,3,2,1] [1,2,3,4,5]
[4,7,8,7,4]

和通常的函数类似，lambda 中也可以应用模式匹配：

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

不同的是，lambda 不支持对同一个参数定义多个模式。

Fold 有点类似于 map 函数，只不过 fold 操作最终会将列表中的元素归并（reduce）到单个值。

Fold 函数接收三个参数：

• binary function：接收两个参数的函数
• 初始值：称作累加器（accumulator）
• 需要被折叠的列表

首先是 binary function 接收 accumulator 和列表的第一个元素作为参数，执行特定的计算后返回一个新的 accumulator；
binary function 继续接收刚返回的新 accumulator 和列表中剩余元素中的第一个作为参数，执行计算并返回新的 accumulator；
若干次循环过后，列表中的最后一个元素被传入 binary function，返回的 accumulator 即为整个列表归并（折叠）后的最终结果。

左折叠 foldl

运用左折叠（从左侧开始折叠）实现自定义的 sum 函数：

Prelude> let sum' xs = foldl (\acc x -> acc + x) 0 xs
Prelude> sum' [3, 5, 2, 1]
11

对应到前面提到的概念，lambda 函数 (\acc x -> acc + x) 即为 binary function，0 是初始值（accumulator），xs 为传入的待折叠列表。

借助 curried function，甚至可以写出更简单的形式：

let sum' = foldl (+) 0

lambda 函数 (\acc x -> acc + x) 实际上等效于 (+)。
对于 xs 参数的化简，原因是通常情况下，若函数具有 foo a = bar b a 这样的形式，则该函数可以简化为 foo = bar b。

运用左折叠实现自定义的 elem 函数：

Prelude> let elem' y ys = foldl (\acc x -> if x == y then True else acc) False ys
Prelude> elem' 2 [1, 2, 3]
True

右折叠 foldr

运用右折叠（从右侧开始折叠）实现自定义的 map 函数：

Prelude> let map' f xs = foldr (\x acc -> f x : acc) [] xs
Prelude> map' (+3) [1, 2, 3]
[4,5,6]

此外还有两个折叠函数 foldl1 和 foldr1。它们与 foldl 和 foldr 的功能基本相同，只不过不需要显式地提供初始值。而是会自动地将列表的第一个值（不管从左起还是从右起）作为初始值。

以下是几个通过 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)

Learn You a Haskell for Great Good!