「Learn Haskell」#2 高阶函数与模块

< #1

#3 >

Higher Order Functions

Currying

Haskell中的函数是柯里化（Currying）的，可以看作所有函数都只接收一个参数，而接收两个参数的函数实际上是这个函数接收了第一个参数后返回了一个接收第二个参数的函数，然后用这个函数接收第二个参数，返回最终的结果。比如max函数，它的类型签名是：

max :: Ord a => a -> a -> a

可以看成a -> (a -> a)，即接收一个参数，返回一个类型为a -> a的函数。比如max 1的类型签名是：

max 1 :: (Ord a, Num a) => a -> a

因此max 1 2，也就等同于(max 1) 2，即将函数max 1应用在数字2上

同时，函数也可以接收函数作为参数，参数有函数的函数就被称为高阶函数（Higher Order Functions）

一些高阶函数

zipWith

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

第一个参数为一个函数，然后接收两个列表，将其对应元素传入接收的函数中，得到的结果组成一个新的列表。如果两个传入的列表长度不同，以最短的列表为准，长列表中超出的元素省略。用例：

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]  

flip

flip :: (a -> b -> c) -> b -> a -> c

flip函数接收一个二元函数，返回一个新的二元函数，将其输入的两个参数顺序反过来：

ghci> zip [1,2,3,4,5] "hello"
[(1,'h'),(2,'e'),(3,'l'),(4,'l'),(5,'o')]
ghci> flip zip [1,2,3,4,5] "hello"  
[('h',1),('e',2),('l',3),('l',4),('o',5)]

map

map :: (a -> b) -> [a] -> [b]

map函数接收一个函数f和一个列表a，将函数f应用在列表a的每个元素中，并返回得到的所有结果组成的列表b：

ghci> map (+3) [1,5,3,1,6]  
[4,8,6,4,9]  

filter

filter :: (a -> Bool) -> [a] -> [a]

filter函数接收一个函数f和一个列表a，将列表a中的每个元素传入函数f中，如果结果为True就保留，结果为False就抛弃，返回所有保留的元素组成的新列表：

ghci> filter even [1..10]  
[2,4,6,8,10] 

takeWhile

takeWhile :: (a -> Bool) -> [a] -> [a]

takeWhile函数接收一个函数f和一个列表a，将列表a中从左向右每个元素传入函数f，直到结果为False停止，返回停止前传入的所有元素组成的新列表：

ghci> takeWhile (/=' ') "word1 word2"
"word1"

Function application

函数应用可以使用$，$是一个函数，它的类型是：

($) :: (a -> b) -> a -> b

它可以改变函数结合优先级，将左侧函数应用于全部右侧内容上，相当于给右侧整体加上了括号。否则函数默认左结合，会依次向右应用而不会应用在整体上。

f $ g x
-- 等价于
f (g x)
-----
f g x
-- 等价于
(f g) x

Function Composition

函数复合可以使用.，.也是一个函数，它的类型是：

(.) :: (b -> c) -> (a -> b) -> a -> c

定义是：

f . g = \x -> f (g x)

但是函数复合的优先级要比函数执行低，比如：

sum . replicate 5 . max 6.7 8.9

会先执行max 6.7 8.9并返回8.9，然后将sum、replicate 5、8.9复合，但两个函数无法和一个值(8.9)复合，所以会抛出异常。因此要使用$来规定先复合再执行：

sum . replicate 5 . max 6.7 $ 8.9

lambda

Haskell语言中的lambda表达式是用\来表示的（因为看着像$\mathtt{\lambda}$？）
具体语法是

\para1 para2 ... -> return

“->”前的 para1 para2 … 是传入参数，单个多个都可以，需要用空格隔开；”->”后的 return 是计算得到的返回值。一般需要用括号将整个表达式括起来，防止返回值部分一直向右延伸。

fold和scan

fold和scan都接收三个参数（一个二元函数，一个初始值accumulator，一个要折叠的列表），fold返回一个值，而scan返回一个列表
传入的二元函数f :: a -> b -> b将accumulator和从列表中取出的值一同传入（l则accumulator在左边为第一个参数，r则accumulator在右边为第二个参数）

foldl

左折叠，每次从列表最左侧取出一个值，和accumulator一起传入二元函数，并且accumulator在左边为第一个参数，如：

foldl f a xs

它的结果计算过程为

> foldl f a [x1, x2, x3]
[1.] a = f a x1
[2.] a = f a x2 = f (f a x1) x2
[3.] a = f a x3 = f (f (f a x1) x2) x3

可以看出 f (f a x1) x2 其实就是 foldl f a [x1, x2]
而且因此，foldl在计算时最外层需要找到x3，这样如果xs是一个无穷列表，那么将无法计算，陷入无穷。所以foldl虽然看起来从左边取值，但是函数需要从右侧展开，并不适用于无穷列表

foldr

右折叠，每次从列表最右侧取出一个值，和accumulator一起传入二元函数，并且accumulator在右边为第二个参数，如：

foldr f a xs

它的结果计算过程为

> foldr f a [x1, x2, x3]
[1.] a = f x3 a
[2.] a = f x2 a = f x2 (f x3 a)
[3.] a = f x1 a = f x1 (f x2 (f x3 a))

从中可以看出 f x2 (f x3 a) 就是 foldr f a [x2, x3]
因此可以使用递归来写一个和foldr效果一样的函数:

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

也可以看出，最外层计算时只需要x1并且向下递归，并不会接触到列表末尾，因此可以用于无穷列表。foldr即使看上去从右边取值，但是要从左开始展开，可以用于无穷列表

例如：

ghci> foldr (||) False (repeat True)
True    -- 由于逻辑运算存在短路，计算值全应为True，所以直接返回了
ghci> foldl (||) False (repeat True)
-- 这里什么都不会发生，直到电脑内存被爆掉
-- 因为函数刚开始就需要列表最右侧的值，所以在不断计算这个无穷列表

scanl和scanr

scan类似fold，只是将中间得到的每一个值都添加进一个列表中并返回这个列表
scanl则向右延伸这个列表，scanr则向左延伸这个列表
但是它和fold恰恰相反，scanl能用于无穷列表，而scanr不能

> scanr f a [x1, x2, x3]
[1.] 最右侧元素(-1 in python) : a
[2.] 右侧第二个元素(-2) : f x3 a
[3.] 右侧第三个元素(-3) : f x2 (f x3 a)
[4.] 右侧第四个元素(-4) : f x1 (f x2 (f x3 a))

可以看出 f x2 (f x3 a) 是 foldr f a [x2, x3]，也是 scanr f a [x2, x3] 的第一个元素
因此可以用递归来写一个和scanr效果一样的函数：

scanr' :: (a -> b -> b) -> b -> [a] -> [b]
scanr' _ x [] = [x]
-- scanr' f a (x:xs) = f x (foldr f a xs) : scanr' f a xs
scanr' f a (x:xs) = f x q : qs
                    where qs@(q:_) = scanr' f a xs

scanl也是同理：

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

也可以看出，scanr返回的列表的第一个元素是最后添加进去的，所以它无法用于无穷列表。而scanl返回的列表中的元素是从左到右依次添加，可以用于无穷列表截取前一部分结果：

ghci> take 10 (scanl (+) 0 [1..])
[0,1,3,6,10,15,21,28,36,45]
ghci> take 10 (scanr (+) 0 [1..])
[*** Exception: stack overflow

使用foldr编写foldl

pdcxs还给我介绍了一个神奇的操作，用foldl来定义foldr：

foldl' f z xs = foldr (\x g y -> g (f y x)) id xs z

它利用 foldr (\x g y -> g (f y x)) id xs 生成一个函数，作用于z得到结果。

先来看一下foldr的类型：

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
-- 可以看成 (a -> b -> b) -> b -> [a] -> b

但是在这个例子中，类型b并不是一个数字，而是一个函数(b -> b)。

所以这里foldr的类型可以写成：

(a -> (b -> b) -> (b -> b)) -> (b -> b) -> [a] -> (b -> b)

对应于用法 foldr (\x g y -> g (f y x)) id xs ，它返回的值应该是一个函数，类型为 b -> b（后面要作用于z）
而xs对应于[a]；id对应于(b -> b)
所以 (\x g y -> g (f y x)) 要对应于：

(a -> (b -> b) -> (b -> b))

因此可以推断出x的类型是a；y的类型是b；而返回的值为一个类型为(b -> b)的函数。

再看，返回的值是 g (f y x) ，其中 f y x 返回的是一个值，类型为b
所以g接收一个类型b，返回一个类型b -> b。即g的类型为：

b -> (b -> b)

现在根据foldr的定义：

foldr f a (x:xs) = f x (foldr f a xs)

带入计算一下：

xs即为[x1..xn]，为了方便，用xs’来表示[x2..xn]，用xs’’来表示[x3..xn]

定义中的f即为(\x g y -> g (f y x))，a即为id

  foldr (\x g y -> g (f y x)) id xs z
= (\x g y -> g (f y x)) x1 (foldr (...) id xs') z

写完第一步，可以发现，x1 (foldr (…) id xs’) z 正好分别对应了lambda表达式中的x、g、y。可以将其应用，进一步展开：

  (\x g y -> g (f y x)) x1 (foldr (...) id xs') z
= (foldr (...) id xs') (f z x1)

不难发现，原式 (foldr (…) id xs) z 等价于：

(foldr (...) id xs') (f z x1)

跟着这个思路，xs每次少一个开头的元素x’，z每次变换成为 f z x’
因此下一步：

  (\x g y -> g (f y x)) x1 (foldr (...) id xs') z
= (foldr (...) id xs') (f z x1)
= (foldr (...) id xs'') (f (f z x1) x2)
= (foldr (...) id xs''') (f (f (f z x1) x2) x3)
= ...

可以发现，已经有了规律。那么最终停止时是什么样呢？

最后到了不能在展开时，最前面的 foldr (…) id xs 已经变成了 foldr (…) id []
而根据前面foldr的定义 foldr _ x [] = x ，它应该返回id

所以最后的结果：
(id的定义：id x = x)

  ...
= (foldr (...) id xs') (f z x1)
= (foldr (...) id xs'') (f (f z x1) x2)
= ...
= (foldr (...) id []) (f (.. (f z x1) ..) xn)
= id (f (.. (f z x1) ..) xn)
= f (.. (f z x1) ..) xn

那么最后这个结果就很熟悉了，它就是 foldl f z xs。
所以我们推导出了这个用foldr表示foldl的写法是正确的。

Modules

Haskell会自动加载Prelude模块（module），如果在GHCi中再加载其他模块，需要使用:m + ...，比如加载Data.List模块：

Prelude> :m + Data.List

而在hs文件中引入模块，需要使用import语句，下面和python的对比可以便于理解：

import Data.List
-- from Data.List import *

import Data.List (nub, sort)
-- from Data.List import nub, sort

import Data.List hiding (nub)
-- 从Data.List中引入所有，但不引入nub函数

import qualified Data.List
-- import Data.List

import qualified Data.List as Li
-- import Data.List as Li

编写Modules

模块中要包含将要使用的一些函数，像正常的hs文件一样写即可，但头部需要有导出语句（export）。比如一个模块文件名叫ModuleA.hs，那它的头部需要写：

module ModuleA
( functionA
, functionB
, functionC
) where

而且文件中的所有函数只导出需要使用的即可。比如该文件中还含有functionD供前三个函数内部使用，那么在import ModuleA之后也无法调用functionD。

Reference

• Learn You a Haskell
• Writing foldl using foldr - StackOverflow
• Haskell：用foldr定义foldl

---

目录

#0 | 总章        
#1 | 基础语法与函数   
#2 | 高阶函数与模块   
#3 | 类型与类型类    
#4 | 输入输出与文件   
#5 | 函子、应用函子与单子
#6 | 半群与幺半群    
#7 | 一些其它类型类   
#A | Haskell与范畴论