max
函数说事吧。它看起来像是取两个参数,回传较大的那个数。 实际上,执行 max 4 5
时,它会首先回传一个取一个参数的函数,其回传值不是 4 就是该参数,取决于谁大。 然后,以 5 为参数调用它,并取得最终结果。 这听着挺绕口的,不过这一概念十分的酷! 如下的两个调用是等价的:max
函数的型别: max :: (Ord a) => a -> a -> a
。 也可以写作: max :: (Ord a) => a -> (a -> a)
。 可以读作 max
取一个参数 a
,并回传一个函数(就是那个 ->
),这个函数取一个 a
型别的参数,回传一个a。 这便是为何只用箭头来分隔参数和回传值型别。mulThree 3 5 9
或 ((mulThree 3) 5) 9
,它背后是如何运作呢? 首先,按照空格分隔,把 3
交给 mulThree
。 这回传一个回传函数的函数。 然后把 5
交给它,回传一个取一个参数并使之乘以 15
的函数。 最后把 9
交给这一函数,回传 135
。 想想,这个函数的型别也可以写作 multThree :: (Num a) => a -> (a -> (a -> a))
,->
前面的东西就是函数取的参数,后面的东西就是其回传值。所以说,我们的函数取一个 a
,并回传一个型别为 (Num a) => a -> (a -> a)
的函数,类似,这一函数回传一个取一个 a
,回传一个型别为 (Num a) => a -> a
的函数。 而最后的这个函数就只取一个 a
并回传一个 a
,如下:GT
。 简单。 注意下在等号两边都有 x
。 想想 compare 100
会回传什么?一个取一数与 100 比较的函数。 Wow,这不正是我们想要的? 这样重写:compare 100
回传函数。compare
的型别为 (Ord a) => a -> (a -> Ordering)
,用 100 调用它后回传的函数型别为 (Num a, Ord a) => a -> Ordering
,同时由于 100 还是 Num
型别类的实例,所以还得另留一个类约束。divideByTen 200
就是 (/10) 200
,和 200 / 10
等价。-
运算符,按照前面提到的定义,(-4)
理应回传一个并将参数减 4 的函数,而实际上,处于计算上的方便,(-4)
表示负 4
。 若你一定要弄个将参数减 4 的函数,就用 subtract
好了,像这样 (subtract 4)
.let
给它命名或传到另一函数中,在 ghci 中直接执行 multThree 3 4
会怎样?a -> a
型别的函数,但它不知道该如何显示它。 函数不是 Show
型别类的实例,所以我们不能得到表示一函数内容的字串。 若在 ghci 中计算 1+1
,它会首先计算得 2
,然后调用 show 2
得到该数值的字串表示,即 "2"
,再输出到屏幕.(->)
是自然的右结合,不过在这里括号是必须的。 它标明了首个参数是个参数与回传值型别都是a的函数,第二个参数与回传值的型别也都是a。 我们可以用 Curried functions 的思路来理解这一函数,不过免得自寻烦恼,我们姑且直接把它看作是取两个参数回传一个值,其首个参数是个型别为 (a->a)
的函数,第二个参数是个 a
。 该函数的型别可以是 (Int->Int)
,也可以是 (String->String)
,但第二个参数必须与之一致。f
当函数,用 x
调用它得到的结果再去调用它。也就可以这样玩:zipWith
。 它取一个函数和两个 List 做参数,并把两个 List 交到一起(使相应的元素去调用该函数)。 如下就是我们的实现:b
,因为这个处理交叉的函数第二个参数的型别是 b
。 回传的 List 中元素型别为 c
。 如果一个函数说取一个型别为 a->b->c
的函数做参数,传给它个 a->a->c
型别的也是可以的,但反过来就不行了。 可以记下,若在使用高阶函数的时候不清楚其型别为何,就先忽略掉它的型别声明,再到 ghci 下用 :t
命令来看下 Haskell 的型别推导.zip
很相似,边界条件也是相同,只不过多了个参数,即处理元素交叉的函数。它关不着边界条件什么事儿,所以我们就只留一个 _
。后一个模式的函数体与 zip
也很像,只不过这里是 f x y
而非 (x,y)
。 只要足够通用,一个简单的高阶函数可以在不同的场合反复使用。 如下便是我们 zipWith'
函数本领的冰山一角:for
、while
、赋值、状态检测来实现功能,再包起来留个接口,使之像个函数一样调用。而函数式语言使用高阶函数来抽象出常见的模式,像成对遍历并处理两个 List 或从中筛掉自己不需要的结果。flip
,flip
简单地取一个函数作参数并回传一个相似的函数,只是它们的两个参数倒了个。a
和 b
,而它回传的函数的参数型别为 b
和 a
。 由于函数缺省都是柯里化的,->
为右结合,这里的第二对括号其实并无必要,(a -> b -> c) -> (b -> a -> c)
与 (a -> b -> c) -> (b -> (a -> c))
等价,也与 (a -> b -> c) -> b -> a -> c
等价。 前面我们写了 g x y = f y x
,既然这样可行,那么 f y x = g x y
不也一样? 这一来我们可以改成更简单的写法:flip' f
而不带 y
和x
,它就会回传一个俩参数倒个的函数。 flip
处理的函数往往都是用来传给其他函数调用,于是我们可以发挥 Curried functions 的优势,预先想好发生完全调用的情景并处理好回传值.a
回传 b
的函数和一组 a
的 List,并回传一组 b
。 这就是 Haskell 的有趣之处:有时只看型别声明就能对函数的行为猜个大致。map
函数多才多艺,有一百万种用法。如下是其中一小部分:map (+3) [1,5,3,1,6]
与 [x+3 | x <- [1,5,3,1,6]
完全等价。p x
所得的结果为真,就将这一元素加入新 List,否则就无视之。几个使用范例:map
和 filter
还是 List Comprehension,选择权归你,看谁舒服用谁就是。 如果有多个限制条件,只能连着套好几个 filter
或用 &&
等逻辑函数的组合之,这时就不如 List comprehension 来得爽了。quicksort
函数么? 我们用到了 List Comprehension 来过滤大于或小于锚的元素。 换做 filter
也可以实现,而且更加易读:map
和 filter
是每个函数式程序员的面包黄油(呃,map
和 filter
还是 List Comprehension 并不重要)。 想想前面我们如何解决给定周长寻找合适直角三角形的问题的? 在命令式编程中,我们可以套上三个循环逐个测试当前的组合是否满足条件,若满足,就打印到屏幕或其他类似的输出。 而在函数式编程中,这行就都交给 map
和 filter
。 你弄个取一参数的函数,把它交给 map
过一遍 List,再 filter
之找到合适的结果。 感谢 Haskell 的惰性,即便是你多次 map
一个 ```List`` 也只会遍历一遍该 List,要找出小于 100000 的数中最大的 3829 的倍数,只需过滤结果所在的 List 就行了."elephants know how to party"
中的首个单词,可以 takeWhile (/=' ') "elephants know how to party"
,回传 "elephants"
。okay,要求所有小于 10000 的奇数的平方的和,首先就用 (^2)
函数 map
掉这个无限的 List [1..]
。然后过滤之,只取奇数就是了。 在大于 10000 处将它断开,最后前面的所有元素加到一起。 这一切连写函数都不用,在 ghci 下直接搞定.map
它,filter
它,切它,直到它符合我们的要求,再将其加起来。 这用 List comprehension 也是可以的,而哪种方式就全看你的个人口味.map
或 filter
一个无限 List,是因为它的操作不会被立即执行,而是拖延一下。只有我们要求 Haskell 交给我们 sum
的结果的时候,sum
函数才会跟 takeWhile
说,它要这些数。takeWhile
就再去要求 filter
和 map
行动起来,并在遇到大于等于 10000 时候停止. 下个问题与 Collatz 串行有关,取一个自然数,若为偶数就除以 2。 若为奇数就乘以 3 再加 1。 再用相同的方式处理所得的结果,得到一组数字构成的的链。它有个性质,无论任何以任何数字开始,最终的结果都会归 1。所以若拿 13 当作起始数,就可以得到这样一个串行 13,40,20,10,5,16,8,4,2,1
。13*3+1
得 40,40 除 2 得 20,如是继续,得到一个 10 个元素的链。chain
函数 map
到 [1..100]
,得到一组链的 List,然后用个限制条件过滤长度大于 15 的链。过滤完毕后就可以得出结果list中的元素个数.map
,我们可以写出类似 map (*) [0..]
之类的代码。 如果只是为了例证 Curried functions 和不全调用的函数是真正的值及其原理,那就是你可以把函数传递或把函数装在 List 中(只是你还不能将它们转换为字串)。 迄今为止,我们还只是 map
单参数的函数到 List,如 map (*2) [0..]
可得一组型别为 (Num a) => [a]
的 List,而 map (*) [0..]
也是完全没问题的。*
的型别为 (Num a) => a -> a -> a
,用单个参数调用二元函数会回传一个一元函数。如果用 *
来 map
一个 [0..]
的 List,就会得到一组一元函数组成的 List,即 (Num a) => [a->a]
。map (*) [0..]
所得的结果写起来大约就是 [(0*),(1*),(2*)..]
.(*4)
等价。 然后用 5
调用它,与 (* 4) 5
或 4*5
都是等价的.\
(因为它看起来像是希腊字母的 lambda -- 如果你斜视的厉害),后面是用空格分隔的参数,->
后面就是函数体。通常我们都是用括号将其括起,要不然它就会占据整个右边部分。numLongChain
函数中用 where
语句声明了个 isLong
函数传递给了 filter
。好的,用 lambda 代替它。(\xs -> length xs > 15)
回传一个函数,它可以告诉我们一个 List 的长度是否大于 15。map (+3) [1,6,3,2]
与 map (\x -> x+3) [1,6,3,2]
等价,(+3)
和 (\x -> x+3)
都是给一个数加上 3。不用说,在这种情况下不用 lambda 要清爽的多。[]
和 (x:xs)
。lambda 的模式匹配若失败,就会引发一个运行时错误,所以慎用!->
,这一来型别声明的写法就很明白了。当然第一段代码更易读,不过第二个函数使得柯里化更容易理解。flip
函数实现了:flip' f x y = f y x
等价,但它可以更明白地表示出它会产生一个新的函数。flip
常用来处理一个函数,再将回传的新函数传递给 map
或 filter
。所以如此使用 lambda 可以更明确地表现出回传值是个函数,可以用来传递给其他函数作参数。(x:xs)
模式,对单个元素和余下的 List 做些事情。这一模式是如此常见,因此 Haskell 引入了一组函数来使之简化,也就是 fold
。它们与map有点像,只是它们回传的是单个值。fold
取一个二元函数,一个初始值(我喜欢管它叫累加值)和一个需要折叠的 List。这个二元函数有两个参数,即累加值和 List 的首项(或尾项),回传值是新的累加值。然后,以新的累加值和新的 List 首项调用该函数,如是继续。到 List 遍历完毕时,只剩下一个累加值,也就是最终的结果。sum
,这次用 fold
替代那复杂的递归:fold
的执行过程:\acc x-> acc + x
是个二元函数,0
是初始值,xs
是待折叠的 List。一开始,累加值为 0
,当前项为 3
,调用二元函数 0+3
得 3
,作新的累加值。接着来,累加值为 3
,当前项为 5
,得新累加值 8
。再往后,累加值为 8
,当前项为 2
,得新累加值 10
。最后累加值为 10
,当前项为 1
,得 11
。恭喜,你完成了一次折叠 (fold)
!(\acc x -> acc + x )
与 (+)
等价。我们可以把 xs
等一应参数省略掉,反正调用 foldl (+) 0
会回传一个取 List 作参数的函数。通常,如果你的函数类似 foo a = bar b a
, 大可改为 foo = bar b
。有柯里化嘛。elem
是检查某元素是否属于某 List 的函数吧,我就不再提了(唔,刚提了)。用左折叠实现它:fold
时,累加值与最终结果的型别总是相同的。如果你不知道怎样对待起始值,那我告诉你,我们先假设它不存在,以 False
开始。我们要是 fold
一个空 List,结果就是 False
。然后我们检查当前元素是否为我们寻找的,如果是,就令累加值为 True
,如果否,就保留原值不变。若 False
,及表明当前元素不是。若 True
,就表明已经找到了。\acc x -> ...
),而右折叠的二元函数参数的顺序正好相反(即 \x acc -> ...
)。这倒也正常,毕竟是从右端开始折叠。fold
实现 map
函数,累加值就是个 List。将 map
处理过的元素一个一个连到一起。很容易想到,起始值就是空 List。(+3)
来映射 [1,2,3]
,它就会先到达 List 的右端,我们取最后那个元素,也就是 3
来调用 (+3)
,得 6
。追加 (:)
到累加值上,6:[]
得 [6]
并成为新的累加值。用 2
调用 (+3)
,得 5
,追加到累加值,于是累加值成了 [5,6]
。再对 1
调用 (+3)
,并将结果 4 追加到累加值,最终得结果 [4,5,6]
。map' f xs = foldl (\acc x -> acc ++ [f x]) [] xs
就行了。不过问题是,使用 (++)
往 List 后面追加元素的效率要比使用 (:)
低得多。所以在生成新 List 的时候人们一般都是使用右折叠。sum
函数的左右折叠实现都是十分相似。不过有个大的不同,那就是右折叠可以处理无限长度的数据结构,而左折叠不可以。将无限 List 从中断开执行左折叠是可以的,不过若是向右,就永远到不了头了。fold
实现。无论何时需要遍历 List 并回传某值,都可以尝试下 fold
。因此,fold
的地位可以说与 map
和 filter
并驾齐驱,同为函数式编程中最常用的函数之一。foldl
和 foldr
相似,只是你无需明确提供初始值。他们假定 List 的首个(或末尾)元素作为起始值,并从旁边的元素开始折叠。这一来,sum
函数大可这样实现:sum = foldl1 (+)
。这里待折叠的 List 中至少要有一个元素,若使用空 List 就会产生一个运行时错误。不过 foldl
和 foldr
与空 List 相处的就很好。所以在使用 fold
前,应该先想下它会不会遇到空 List,如果不会遇到,大可放心使用 foldr1
和 foldl1
。fold
的威力,我们就用它实现几个库函数:head
函数和 last
函数,而且效率也很高。这里只是为了演示,用 fold
的实现方法。我觉得我们这个 reverse'
定义的相当聪明,用一个空 List 做初始值,并向左展开 List,从左追加到累加值,最后得到一个反转的新 List。\acc x -> x : acc
有点像 :
函数,只是参数顺序相反。所以我们可以改成 foldl (flip (:)) []
。f
,起始值 z
,如果从右折叠 [3,4,5,6]
,实际上执行的就是 f 3 (f 4 (f 5 (f 6 z)))
。f
会被 List 的尾项和累加值调用,所得的结果会作为新的累加值传入下一个调用。假设 f
是 (+)
,起始值 z
是 0
,那么就是 3 + (4 + (5 + (6 + 0)))
,或等价的首码形式:(+) 3 ((+) 4 ((+) 5 ((+) 6 0)))
。相似,左折叠一个 List,以 g
为二元函数,z
为累加值,它就与 g (g (g (g z 3) 4) 5) 6
等价。如果用 flip (:)
作二元函数,[]
为累加值(看得出,我们是要反转一个 List),这就与 flip (:) (flip (:) (flip (:) (flip (:) [] 3) 4) 5) 6
等价。显而易见,执行该表达式的结果为 [6,5,4,3]
。foldl
和 foldr
相似,只是它们会记录下累加值的所有状态到一个 List。也有 scanl1 和 scanr1。scanl
时,最终结果就是 List 的最后一个元素。而在 scanr
中则是第一个。scan
可以用来跟踪 fold
函数的执行过程。想想这个问题,取所有自然数的平方根的和,寻找在何处超过 1000? 先map sqrt [1..]
,然后用个 fold
来求它们的和。但在这里我们想知道求和的过程,所以使用 scan
,scan
完毕时就可以得到小于 1000 的所有和。所得结果 List 的第一个元素为 1,第二个就是 1+根2,第三个就是 1+根2+根3。若有 x
个和小于 1000,那结果就是 x+1
。$
的优先级则最低。用空格的函数调用符是左结合的,如 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
。因为 $
有最低的优先级,所以你可以把$看作是在右面写一对括号的等价形式。sum (filter (> 10) (map (*2) [2..10]))
该如何?嗯,$
是右结合,f (g (z x))
与 f $ g $ z x
等价。所以我们可以将 sum (filter (> 10) (map (*2) [2..10])
重写为 sum $ filter (> 10) $ map (*2) [2..10]
。$
还可以将数据作为函数使用。例如映射一个函数调用符到一组函数组成的 List:x
调用这一函数,就与用 x
调用 g
再用所得的结果调用 f
等价。f
的参数型别必须与 g
的回传型别相同。所以得到的组合函数的参数型别与 g
相同,回传型别与 f
相同。表达式 negate . (*3)
回传一个求一数字乘以 3 后的负数的函数。f (g (z x))
与 (f . g . z) x
等价。按照这个思路,我们可以将sum (replicate 5 (max 6.7 8.9))
可以重写为 (sum . replicate 5 . max 6.7) 8.9
或 sum . replicate 5 . max 6.7 $ 8.9
。在这里会产生一个函数,它取与 max 6.7
同样的参数,并使用结果调用 replicate 5
再用 sum
求和。最后用 8.9
调用该函数。不过一般你可以这么读,用 8.9 调用 max 6.7
,然后使它 replicate 5
,再 sum
之。如果你打算用函数组合来替掉那堆括号,可以先在最靠近参数的函数后面加一个 $
,接着就用 .
组合其所有函数调用,而不用管最后那个参数。如果有这样一段代码: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]
。如果表达式以 3 个括号结尾,就表示你可以将其修改为函数组合的形式。xs
。由于有柯里化 (Currying),我们可以省掉两端的 xs
。foldl (+) 0
回传的就是一个取一 List 作参数的函数,我们把它修改为 sum' = foldl (+) 0
,这就是 point free style。下面这个函数又该如何改成 point free style 呢?x
是不行的,函数定义中 x
的右边还有括号。cos (max 50)
是有错误的,你不能求一个函数的余弦。我们的解决方法就是,使用函数组合。let
语句给中间的运算结果绑定一个名字,或者说把问题分解成几个小问题再组合到一起。这样一来我们代码的读者就可以轻松些,不必要纠结那巨长的函数组合链了。map
和 filter
那节中,我们求了小于 10000 的所有奇数的平方的和。如下就是将其置于一个函数中的样子: