Haskell学习笔记(三)——高阶函数

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

七、Meta Function

1. Curried functions

本质上,Haskell 的所有函数都只有一个参数,那么我们先前编那么多含有多个参数的函数又是怎么回事?哈!所有多个参数的函数都是 Curried functions。就拿我们的好朋友max 函数说事吧。它看起来像是取两个参数,返回较大的那个数。实际上,执行 max 4 5 时,它会首先返回一个取一个参数的函数,然后,以 5 为参数调用它,并取得最终结果。所以,如下的两个调用等价:

ghci> max 4 5
5
ghci> (max 4) 5
5

把空格放到两个东西之间,称作函数调用。它有点像个运算符,并拥有最高的优先级。看看 max 函数的类型:max :: (Ord a) => a -> a -> a 。也可以写作:max :: (Ord a) => a -> (a -> a)。max 取一个 a 类型的参数,并返回一个函数,这个函数取一个 a 类型的参数,返回一个 a 类型的结果。这便是为何只用箭头来分隔参数和返回值类型的原因。

这样的好处又是如何?简言之,我们若以不全的参数来调用某函数,就可以得到一个不全调用的函数。例如,搞个取一数与 100 比较大小的函数,大可这样:

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

想想 compare 100 会返回什么?一个取一数与 100 比较的函数。这
不正是我们想要的?这样重写:

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

类型声明依然相同,因为 compare 100 返回函数。compare 的类型为
(Ord a) => a -> (a -> Ordering),用 100 调用它后返回的函数类型为
(Num a,Ord a) => a -> Ordering,同时由于 100 还是 Num 类型类的实
例,所以还得另留一个类约束。

中缀函数也可以不全调用,用括号把它和一边的参数括在一起就行了。这返回一个取一参数并将其补到缺少的那一端的函数。一个简单函数如下:

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

 


2. Functions as arguments

我们弄个取一个函数并调用它两次的函数:

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

首先注意类型声明里的括号,因为 (->) 是自然的右结合,所以在这里括号是必须的。它标明了首个参数是个参数与返回值类型都是 a 的函数,第二个参数与返回值的类型也都是 a。

一些调用的例子:

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 取一个函数和两个 List 做参数,并把两个 List 交到一起 (使相
应的元素去调用该函数):

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


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' :: (a -> b -> c) -> (b -> a -> c)
flip' f = g
    where g x y = f y x

--- 利用Curry化,可以这样写
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]

mapfilter

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


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]
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"

 


3. lambda

编写匿名函数,就写个 \ (因为它看起来像是希腊字母的 lambda – 如果你斜视的厉害),后面是用空格分隔的参数,-> 后面就是函数体。通常我们都是用括号将其括起,要不然它就会占据整个右边部分。

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]

同普通函数一样,lambda 中也可以使用模式匹配,只是无法为一个参数设置多个模式,如 [] 和 (x:xs)。lambda 的模式匹配若失败,就会引发一个运行时错误。慎用!

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

一般情况下,lambda 都是括在括号中,除非我们想要后面的整个语句都作为 lambda 的函数体。有趣的是,由于有Curry化,如下的两段是等价的:

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

这样的函数声明与函数体中都有 ->,这一来类型声明的写法就很明白了。当然第一段源代码更易读,不过第二个函数使得Curry化更容易理解。有些时候用这种语句写还是挺酷的,比如,这应该是最易读的 flip 函数实现了:

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

尽管这与 flip' f x y = f y x 等价,但它可以更明白地表示出它会产
生一个新的函数。

 


4. Fold

学习递归时,我们会发现处理 List 的许多函数都有固定的模式,通常我们会将边界条件设置为空 List,再引入 (x:xs) 模式,对单个元素和余下的 List 做些事情。这一模式是如此常见,因此 Haskell 引入了一组函数来使之简化,也就是 fold。

一个 fold 取一个二元函数,一个初始值 (累加值) 和一个需要折叠的 List。这个二元函数有两个参数,即累加值acc 和 List 的首项 (或尾项),返回值是新的累加值。然后,以新的累加值和新的 List 首项调用该函数,如是继续。到 List 遍历完毕时,只剩下一个累加值,就是最终的结果。

首先看下 foldl 函数,也叫做左折叠。它从 List 的左端开始折叠:

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

ghci> sum' [3,5,2,1]
11

考虑到Curry化,我们还可以写出更简单的实现:

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

再用左折叠实现elem函数,这里的 acc 初值应该是 False:

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

右折叠 foldr 的行为与左折叠相似,只是累加值是从 List 的右边开始。同样,左折叠的二元函数取累加值作首个参数,当前值为第二个参数 (即\acc x -> ...),而右折叠的二元函数参数的顺序正好相反 (即 \x acc ->...)。

我们可以用右 fold 实现 map 函数,累加值就是个 List。将 map 处理过的元素一个一个连到一起。很容易想到,起始值就是空 List。

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

当然,我们也完全可以用左折叠来实现它,map' f xs = foldl (\acc x -> acc ++ [f x]) [] xs 就行了。不过问题是,使用 (++) 往 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)

reverse’ 中的\acc x -> x : acc 有点像 : 函数,只是参数顺序相反。所以我们可以改成 foldl (flip (:)) [],相当漂亮的一个实现,不是吗?

foldl1foldr1 的行为与 foldl 和 foldr 相似,只是无需明确提供初始值。它们假定 List 的首个 (或末尾) 元素作为起始值,并从旁边的元素开始折叠。这一来,sum 函数大可这样实现:sum = foldl1 (+)。这里待折叠的 List 中至少要有一个元素,若使用空 List 就会产生一个运行时错误。

scanlscanr 与 foldl 和 foldr 相似,只是它们会记录下累加值的
所有状态到一个 List。也有 scanl1scanr1。当使用 scanl 时,最终结果就是 List 的最后一个元素。而在 scanr 中则是第一个。

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]]

ghci> take 10 (scanl (+) 0 [1..])
[0,1,3,6,10,15,21,28,36,45]

 


5. Function $

接下来看看 $ 函数,也叫作函数调用符。它的定义:

($) :: (a -> b) -> a -> b
f $ x = f x

什么鬼东西?它只是个函数调用符罢了?不全是,但差不多。普通的函数调用符有最高的优先级,而 $ 的优先级则最低。用空格的函数调用符是左结合的,如 f a b c((f a) b) c 等价,而 $ 则是右结合的。

我们可以把 $ 看作是在右面写一对括号的等价形式,它可以减少我们源代码中括号的数目。试想有这个表达式:sum (map sqrt [1..130])。由于低优先级的 $,我们可以将其改为 sum $ map sqrt [1..130],可以省敲不少键!sqrt 3 + 4 + 9 会怎样?这会得到 9, 4 和根号 3 的和。若要取 (3+4+9) 的平方根,就得 sqrt( 3+4+9) 或用 sqrt $ 3+4+9

除了减少括号外,$ 还可以将数据作为函数使用。例如映射一个函数调
用符到一组函数组成的 List:

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

 


6. Function composition

在数学中,函数组合是这样定义的:

$(f\circ g)(x)=f(g(x))$

Haskell 中的函数组合与之很像,即 . 函数。其定义为:

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

注意下类型声明,f 的参数类型必须与 g 的返回类型相同。所以得到的组合函数的参数类型与 g 相同,返回类型与 f 相同。

函数组合是右结合的,我们同时组合多个函数。表达式 f (g (z (x))) 与 (f . g . z) x 等价。比如:

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

不过含多个参数的函数该怎么办?好,我们可以使用不全调用使每个
函数都只剩下一个参数,例如:

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]

函数组合的另一用途就是定义 point free style (也称作 pointless style) 的函数。比如:

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

可以改成:

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

漂亮!point free style 会令我们去思考函数的组合方式,而非数据的传递方式,更加简洁明了。我们可以将一组简单的函数组合在一起,使之形成一个复杂的函数。不过函数若过于复杂,再使用 point free style 往往会适得其反,因此构造较长的函数组合链是不被鼓励的。更好的解决方法,就是使用 let 给中间的运算结果绑定一个名字,把问题分解成几个小问题再组合到一起。

如果我们要求小于 10000 的所有奇数的平方和,有三种实现方式:

--- trivial 实现
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

 

此条目发表在函数式语言分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注