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