文章目录
高阶函数
haskell中的函数可以接受函数作为参数，也可以将函数作为返回值，这样的函数叫做高阶函数。他们是解决问题、简化代码的得力工具，在haskell这类函数式编程语言中它不可或缺。
5.1 柯里函数
多元参数?哈哈
- 本质上,haskell所有的函数都只有一个参数
- 所有在前面笔记中出现过的多参数函数都是柯里函数: 不一次性取完所有参数,而是在每次调用时只取得一个参数,并返回一个一元函数来接收下一个参数,以此类推
|
1 2 3 4 5 6 7 8 9 10 |
ghci :t max max :: (Ord a)=> a -> a -> a -- 也可以写成这样 max :: (Ord a)=> a->(a->a) --下面两种调用也因此是等价的 ghci> max 4 5 ghci> (max 4) 5 |
好处
- 这样一来,就可以以部分的参数来调用某函数,得到一个部分应用(partial application)函数
- 这样构造的函数简单快捷,且结果随时可以传递给其他函数构造出新的函数
利用好处
|
1 2 3 4 |
-- 看这个函数,简单至极 multThree :: Int -> Int -> Int -> Int multThree x y z=x*y*z |
- 返回参数类型的逐步解析
- multThree :: Int ->(Int->(Int->Int))
- Int->(Int->Int)
- Int->Int
- Int
以下例子将会演示如何通过少调参数调用函数来创建新的函数
|
1 2 3 4 |
ghci> let multTwoWithNine = multThree 9 ghci> multTwoWithNine 2 3 54 |
5.1.1 截断
- 通过截断,可以对中缀函数进行部分应用 ,将一个参数放在中缀函数的一侧,并在外面用括号括起来,即可截断这个中缀函数
- 使用截断时,唯一需要注意的是:在haskell中
(-4)表示的是负四,想要表示减去一个参数的函数,可以用(substract 4)实现
|
1 2 3 |
divideByTen :: (Floating a)=>a->a divideByTen =(/10) |
5.1.2 打印函数
在haskell中,想要打印一个函数,必须要调用show函数,只有返回值是show类型的实例,才可能显示到屏幕
5.2 再来点高阶函数
|
1 2 3 |
applyTwice :: (a->a)->a->a applyTwice f x = f (f x) |
- haskell中
->是自然的右结合,一般使用不需要使用括号,然而以上的括号是必须的 - 它标明了第一个参数是一个参数和返回值类型都是a的函数,第二个参数与返回值的类型也都是a
5.2.1 实现ZipWith
ZipWith函数
此函数取一个函数和两个列表作为参数,然后使用两个列表中相应的元素取调用该函数,将两个表结合到一起
实现
|
1 2 3 4 5 |
zipWith' :: (a->b->c)->[a]->[b]->[c] zipWith' _ [] _ = [] zipWith' _ _ [] = [] zipWith' f (x:xs) (y:ys) = f x y :zipWith' f xs ys |
在haskell中,在编写函数(尤其是高阶函数)时如果拿不准函数的类型,可以先省略类型,再用:t查看haskell类型推导的结果
5.2.2 实现flip
- flip函数简单的取一个函数作为参数,返回一个效果相同的新函数
- 唯一的区别是新旧函数的前两个参数的顺序是颠倒的
|
1 2 3 4 |
flip' :: (a->b->c)->(b->c->a) flip' f = g where g x y =f x y |
- flip处理过的函数一般都用来传给其他函数
- 我们可以在处理高阶函数时,发挥柯里函数的优势,预先考虑清楚全情景的应用
- 根据返回值的要求,传递合适的函数
5.3 函数式程序员工具箱
因为:
– 身为函数式程序员,很少需要对单个值多费心思
– 更多的情景是处理一系列字母或者其他类型的数据
– 通过转换这一类集合来求取最后的结果
于是:
我们很可能需要以下这些函数
5.3.1 map函数
概述
map函数取一个函数和一个列表作为参数,将这个函数应用到该列表的每个元素,产生一个新的列表
|
1 2 3 4 5 |
--定义 map :: (a->b)->[a]->[b] map _ []=[] map f (x:xs) = f x : map f xs |
更多用法
|
1 2 3 4 5 6 7 8 9 10 11 |
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] |
5.3.2 filter函数
概述
- filter函数取一个谓词(predicate)和一个列表,返回由列表中所有符合该条件的元素组成的列表
- 谓词值返回值为布尔值的函数
|
1 2 3 4 5 6 |
filter :: (a->Bool)->[a]->[a] filter _ [] = [] filter p (x:xs) | p x = x : filter p xs | otherwise =filter p xs |
更多用法
|
1 2 3 4 5 6 7 8 9 10 11 |
ghci> filter (>3) [1,3,5,7,9] [5,7,9] ghci filter (==3) [1,2,3,4,5] [3] ghci> filter even [1..10] [2,4,6,8,10] ghci> let noNULL x = not (null x) in filter noNULL [[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" |
相对于带有多个谓词的列表推导式而言,filter需要进行多次过滤,或者通过逻辑函数&&来组合谓词,才能达到和列表推导式相同的效果
|
1 2 3 4 5 6 7 |
quicksort :: Integer quicksort [] = [] quicksort (x:xs) = let smallerOrEqual = filter (<=x) xs larger = filter (>x) xs in quicksort smallerOrEqual ++ [x] ++ quicksort larger |
5.3.3 有关map与filter的更多示例
|
1 2 3 |
ghci> takeWhile (/=' ') "elephants know how to party" "elephants" |
由于haskell的多参数实现原理,这种现象便变得很容易理解
克拉兹序列
定义如下:
- 从自然数开始
- 如果是1,停止
- 如果是偶数,除以二
- 如果是奇数,将它乘以3然后加1
- 取所得结果,重复以上算法
|
1 2 3 4 5 6 7 8 9 10 11 12 |
chain :: Integer -> [Integer] chain 1 =[1] chain n | even n = n : chain(n 'div' 2) | odd n = n : chain(n*3+1) --以上是生成链的函数 numLongChains :: Int numLongChains = length (filter isLong (map chain [1..100])) where isLong xs=length xs>15 |
这个函数的类型为numLongChains :: Int 这是因为Int类型处理出的类型为Int,可以使用fromInterval函数来处理所得结果以生成Num a
5.4 lambda
概念
- lambda就是一次性的匿名函数
- 有些时候需要传给高阶函数一个特定功能的函数,就会用到lambda
- lambda是一个表达式,因此我们可以将任意将其传给函数
说明
- 使用lambda,就写一个(因为它看起来像是希腊字母入–斜着看)后面跟着函数的参数列表,参数之间使用空格分隔,->后面是函数体,通常习惯使用括号将lambda括起来
- 不熟悉柯里函数和部分应用的初学者可能很容易使用lambda,然而事实上大部分lambda没有必要
|
1 2 3 4 |
--一个实例 numLongchains :: Int numLongChains = length (filter (\xs->length xs>15) (map chain [1..100])) |
- lambda可以取多个参数
- 可以在lambda中使用一个模式的模式匹配
- 只要lambda的模式匹配失效,就会引发运行时错误,所以务必慎用
- 当编写不带括号的lambda时,编译器会假定->右侧都是lambda函数体
|
1 2 3 4 5 |
addThree :: Int->Int->Int->Int --以下两个函数等价 addThree \x->\y->\z->x+y+z addThree x y z =x+y+z |
上面两个等价的函数,前者更好的理解柯里化.下面一个更加直观易懂
优秀案例
|
1 2 3 |
filp' :: (a->b->c)->a->b->c filp' f = \x y -> f y x |
5.5 折叠纸鹤
概述
回顾haskell中的递归,不难发现处理列表的函数大多数拥有(x:xs)这样的固定模式:
这一模式如此常见,以至于haskell设计者直接引入了折叠函数(fold)函数:允许我们将一个数据结构约为单个值
用法
- 一个折叠取一个二元函数(取两个参数的函数),一个初始值(通常称为累加值)以及一个待折叠的列表
- 可以从左开始折叠,也可以从右开始折叠
- 折叠函数会取初始值和列表的起始元素来应用二元函数,得到的返回值作为新的累加值,然后继续重复这一操作,到遍历完毕时,得到的累加值就是最终的结果
5.5.1 使用foldl进行左折叠
|
1 2 3 4 5 6 7 8 |
sum' :: (Num a)=>[a]->a sum' xs = foldl (\acc x->acc+x) 0 xs --另一个例子 sum' :: (Num a) => [a] -> a sum' =foldl (+) 0 |
通常,因为柯里化,foo a=bar b a形式的函数都可以改为foo =bar b
5.5.2 通过foldr进行右折叠
- 左右折叠类似,不过考虑到
:和++的效率及haskell的常见模式,还是使用右折叠更是多一些 - 另外,左折叠无法处理无限列表
|
1 2 3 4 5 6 7 8 |
--以下是几个右折叠的应用 map' :: (a->b)->[a]->[b] map' f xs = foldr (\x acc -> f x:acc) [] xs elem' :: (Eq a)=>a->[a]->bool elem' y ys = foldr (\x acc->if x==y then True else acc) False ys |
5.5.3 flodl1与flodr1函数
- 与前两者非常相似,只不过他们不需要提供初元素,默认为零(实际是取列表第一个元素作为初始值)
- 于是带折叠列表必须不为空
5.5.4 折叠的几个例子
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
reverse' :: [a]->[a] reverse' = flodl (\acc x-> x:acc) [] reverse'' :: [a]->[a] reverse'' = foldl (flip (:)) [] product' :: (Num a)=> [a]->a product' = foldl (*) 1 filter' :: (a->Bool)->[a]->[a] filter' f = flodr (\x acc->if f x then x : acc else acc) [] last' :: [a]->a last' = foldl1 (\_ x ->x) |
5.5.6 无限列表的折叠
无限列表只能运用右折叠,且利用了逻辑运算符的短路特性
5.5.7 扫描
- scanl和scanr和foldl和foldr相似,不过他们会将累加值的变化记录记录到列表中
- scanl1和scanr1相当于flodl1和flodr1
- 扫描可以用于跟踪基于折叠实现的函数执行过程
takeWhile函数可以实现到某条件时的截断
5.6 有$的函数应用
$函数,又称为函数应用符(function application operator)
|
1 2 3 |
($) :: (a->b)->a->b f $ x = f x |
- 普通的,用空格隔开的函数的应用有着最高的优先级,而使用
$运算符的函数有着最低的优先级 - 普通函数,函数调用是从左到右结合的,而
$是右结合的 - 此运算符可以帮助减少表达式中括号的数目
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
-- 几个例子 ghci> sum (filter (>10) (map (*2) [2..10])) 80 ghci> sum $ filter (>10) (map (*2) [2..10]) 80 ghci> sum $ filter (>10) $ map (*2) [2..10] 80 ghci> map ($ 3) [(4+),(10*),(^2),sqrt] [7.0,30.0,9.0,1.7320508075688772] |
5.7 函数组合
**函数组合(function composition)*是这样定义的:(f·g)(x)=f(g(x))
|
1 2 3 4 |
--以下是haskell里的函数组合 (.) :: (b->c)->(a->b)->a->c f . g =\x ->f (g x) |
理所当然但是仍然值得注意的是:f的返回类型需要和g的参数类型相符合
|
1 2 3 4 5 6 7 |
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] |
5.7.1 带有多个参数函数的组合
对于带有多个参数的函数,可以使用部分应用使得其变成只有一个参数的函数,在使用.符号进行函数组合
|
1 2 3 4 5 6 7 8 |
sum (replicate 5 (max 6.7 8.9)) --可以写为 ( sum . replicate 5)(max 6.7 8.9) replicate 2 (product (map (*3) (zipWith max [1,2] [4,5]))) --可以使用以下方式减少括号的数量 replicate 2 . product . map (*3) $ zipWith max [1,2] [4,5] |
5.7.2 Point-Free风格
函数组合的另一用处是pointfree(即pointless风格)的函数
|
1 2 3 4 5 6 |
sum' :: (Num a)=>[a]->a sum' = fold (+) 0 fn x = celling . negate . tan . cos . max 50 --使用point-free风格的代码往往风格更加简洁和易读 |