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]
map
与 filter
:
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 (:)) []
,相当漂亮的一个实现,不是吗?
foldl1
与 foldr1
的行为与 foldl 和 foldr 相似,只是无需明确提供初始值。它们假定 List 的首个 (或末尾) 元素作为起始值,并从旁边的元素开始折叠。这一来,sum 函数大可这样实现:sum = foldl1 (+)
。这里待折叠的 List 中至少要有一个元素,若使用空 List 就会产生一个运行时错误。
scanl
和 scanr
与 foldl 和 foldr 相似,只是它们会记录下累加值的
所有状态到一个 List。也有 scanl1
和 scanr1
。当使用 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