CIS 194 Week 2
28 January, 2015
第一节中没有介绍本地变量。现在，我们来看几个本地变量的例子，会对你们的作业有所帮助。
let 表达式
用 let 来定义表达式范围内的本地变量：
strLength :: String -> Int
strLength [] = 0
strLength (_:xs) = let len_rest = strLength xs in
len_rest + 1
这个例子中的本地变量有点多余（较好的写法是 1 + strLength xs），但是足够演示
let 的用法，不要忘了变量定义之后的 in！
where 从句
用 where 来定义多个分支范围内的本地变量：
frob :: String -> Char
frob [] = 'a' -- len is NOT in scope here
frob str
| len > 5 = 'x'
| len < 3 = 'y'
| otherwise = 'z'
where
len = strLength str
注意变量 len 可以在 where 上方的各个选择分支内使用，但是不能在另一个顶层定义
frob [] = 'a' 中使用。比起 let，Haskell 中更常使用 where，
因为它可以让程序员第一次看到函数时，首先关注函数本身做了什么，而不是先看到一堆本地变量的定义。
Haskell 的布局
Haskell 是对空白字符敏感的语言，这和其他大多数仅把空白字符用来分割标示符的语言形成鲜明对比。 （这点 Haskell 和 Python 相似。）Haskell 中缩进层次指示了代码块结束和新语句开始的位置。 基本上，当一个所谓的布局暗示出现的时候，GHC 会看下一个位置并记住其缩进层次。 如果下一行缩进相同则被认为是同一组代码，如果下一行缩进更少则不认为是同一组。
布局暗示包括 where、let、do、of 和 case。
Haskell 模块总是以 module Name where 开头，表明布局规则对整个文件里的定义都起效。
所以下面这样的定义有误：
x :: Int
x =
5
问题出在 5 和其他顶层定义缩进相同（零缩进），所以 GHC 认为这是一个新的定义而不是 x 定义的一部分。
布局规则常常给 Haskell 新手带来困扰。如果你在以后遇到麻烦，回来重新看这里（或者其他网络资料）—— 通常，多仔细想一想你就明白是怎么一回事了。
在计算缩进层次的时候，代码中的制表符（你没写对吧？！？）被认为是 8 个字符的长度， 而不一定是编辑器显示给你的长度。这种潜在的混乱使得制表符在 Haskell 缩进中被认为是很不好的用法。
累加器
Haskell 中重复给定计算的方法之一是递归。递归也是解决很多问题的最自然的解法。
但是有时候问题的结构并不完全符合 Haskell 的结构。比如我们有一组数字的列表 [Int]。
我们想累加列表中数字的和，但是超过 20 就停止，忽略之后的数字。
因为列表上的递归是从后向前计算结果的，所以通常的递归并不符合我们的要求。
随着列表的深入，我们需要即时跟踪当前的和，这个和就叫做累加器。
这是解决上面问题的代码：
sumTo20 :: [Int] -> Int
sumTo20 nums = go 0 nums -- the acc. starts at 0
where go :: Int -> [Int] -> Int
go acc [] = acc -- empty list: return the accumulated sum
go acc (x:xs)
| acc >= 20 = acc
| otherwise = go (acc + x) xs
sumTo20 [4,9,10,2,8] == 23
多态函数的一个重要的特点是调用者决定其类型。 当你写一个多态函数时，它应该对所有可能的输入类型都工作。 这连同 Haskell 无法只根据某表达式的类型直接做决定的事实，产生了一些有趣的意味（？）。
对初学者来说，下面的代码很假:
bogus :: [a] -> Bool
bogus ('X':_) = True
bogus _ = False
假是因为 bogus 的定义实际上假定了输入是 [Char]。
这个函数并不能对任意类型的 a 都奏效。
相反，下面的代码则没有问题：
notEmpty :: [a] -> Bool
notEmpty (_:_) = True
notEmpty [] = False
notEmpty 函数并不关心 a 是什么就能工作。
这种“不关心”就是参数多态中“参数化（parametric）”的含义。
所有的 Haskell 函数实现对于它的类型都必须是参数化的；函数不能介意或者基于这些类型参数做选择。
函数不能在 a 是 Int 时做一种事，而在 a 是 Bool 时做另一种事。
Haskell 不允许这样。这种语言特性叫做参态（parametricity）。
参态有一些很深刻的意义。其中之一叫做类型擦除。 因为 Haskell 程序运行的时候不能再根据类型信息做决定，所以所有的类型信息在编译期间就可以被丢弃掉了。 不管类型对于 Haskell 代码来说多么重要，他们和运行中的程序都没有关系。 这个特性给 Haskell 带来了相比其他需要在运行时保留类型信息的语言（比如 Python）巨大的速度提升。 （类型擦除并不是唯一让 Haskell 比其他语言更快的方法，但 Haskell 有时候能比 Python 快 20 倍。）
参态的另一个影响是它限制了多态函数的实现。例如下面的类型签名：
strange :: a -> b
strange 函数获得一个类型是 a 的东西返回另一个类型是 b 的东西。
但是关键是，它不能得知 a 和 b 具体是什么。所以根本没有办法写出这样的 strange！
strange = error "impossible!"
（Prelude 中定义的 error 函数可以终止整个程序并显示指定信息。）
再来看看
limited :: a -> a
这个函数对于给定的 a 返回 a。只有唯一的 a 它能产生，就是它获得的那个！
所以 limited 只可能有一种实现：
limited x = x
总的来说，给定一个函数的类型，只根据参态就可以推断出该函数的很多特性。 函数可以有多种产生输出值的方式，但是给定输出类型的值应从何而来？ 通过试图回答这个问题，可以获得对函数的一些了解。
考虑下面的多态类型：
[a] -> a
什么样的函数有这样的类型？这个类型说明了给定一个 a 的列表，函数必须产生一个类型为 a 的值。
例如，Prelude 里的函数 head 即是此类型。
[a] -> a
糟糕！好像除此之外没有别的选择了，因为这个函数必须能对所有类型工作。 没有办法凭空造出来一个任意类型的值。
head 就是俗称的partial 函数：对于某些输入不能工作。
函数在某些输入上会无限递归也称做 partial。
函数在所有可能的输入上都有良好的定义叫做total 函数。
好的 Haskell 实践当然是尽量避免 partial 函数。 这也是任何编程语言中的良好实践 —— 但是在决大多数语言中非常麻烦。 而在 Haskell 中往往简单又合理。
**head 是个错误！**它不应该存在 Prelude 中。
其他你应该尽力避免的 Prelude 中的 partial 函数包括 tail、init、last 和 (!!)。
从现在开始在作业中使用其中任意一个都会丢掉样式分！
那应该怎么做？
替换 partial 函数
像 head、tail 等等 partial 函数常常可以被模式匹配取代。比如下面两个定义：
doStuff1 :: [Int] -> Int
doStuff1 [] = 0
doStuff1 [_] = 0
doStuff1 xs = head xs + (head (tail xs))
doStuff2 :: [Int] -> Int
doStuff2 [] = 0
doStuff2 [_] = 0
doStuff2 (x1:x2:_) = x1 + x2
这两个函数做的同样的事，而且也都是 total 的。但是只有第二个显然是 total 的，而且更易读。
对于 [a] 我们会做什么？有几种可能：
-
对列表中的每一个元素做某种操作
-
基于某种测试，只保留一些元素，丢掉其他的
-
对所有元素做“总结”（比如求和、求积、求最大值）
-
你能想到的其他的！
映射（Map）
让我们来考虑第一种情况（对列表中的每一个元素做某种操作）。 比如我们可以对列表中的每一个元素加一：
addOneToAll :: [Int] -> [Int]
addOneToAll [] = []
addOneToAll (x:xs) = x + 1 : addOneToAll xs
或者对每一个取绝对值得到一个非负的列表：
absAll :: [Int] -> [Int]
absAll [] = []
absAll (x:xs) = abs x : absAll xs
或者对每一个平方：
squareAll :: [Int] -> [Int]
squareAll [] = []
squareAll (x:xs) = x^2 : squareAll xs
现在，你脑中应该有红灯作闪警报乱响了。 这几个函数这么相像，应该有什么办法把这种共性抽象出来，省去我们的重复工作。
确实有这么一种办法。你有没有看出来，这三个例子里哪些部分是相同的，哪些部分变化了？
变化的，当然是我们对每个元素做的操作。我们可以把这个操作特化为一个类型为 a -> a 的函数。
现在我们看到了把函数当做函数的输入的大用途！
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
现在我们可以用 map 来实现 addOneToAll、absAll 和 squareAll:
exampleList = [-1, 2, 6]
map (+1) exampleList
map abs exampleList
map (^2) exampleList
过滤（Filter）
另一种常见的模式是，我们只想根据某种测试保留列表中的部分元素，扔掉其他的。 比如我们只想保留所有的正数：
keepOnlyPositive :: [Int] -> [Int]
keepOnlyPositive [] = []
keepOnlyPositive (x:xs)
| x > 0 = x : keepOnlyPositive xs
| otherwise = keepOnlyPositive xs
或者只保留所有的偶数：
keepOnlyEven :: [Int] -> [Int]
keepOnlyEven [] = []
keepOnlyEven (x:xs)
| even x = x : keepOnlyEven xs
| otherwise = keepOnlyEven xs
如何抽象这种模式？哪一部分是不变的，需要抽象出来？
需要抽象出来的应是用来决定哪些值该保留下来的测试（或者说断言）这部分。
断言是一个类型为 a -> Bool 的函数，对应当保留的值返回 True，应当忽略的值返回 False。
filter :: (a -> Bool) -> [a] -> [a]
filte _ [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs
折叠（Fold）
还有一个列表上的递归模式我们还没有说到：折叠。下面是几个模式相似的列表上的函数： 所有函数都试图“结合”列表中的所有元素来得到一个值。
sum' :: [Int] -> Int
sum' [] = 0
sum' (x:xs) = x + sum' xs
product' :: [Int] -> Int
product' [] = 1
product' (x:xs) = x * product' xs
length' :: [a] -> Int
length' [] = 0
length' (_:xs) = 1 + length' xs
这几个函数有什么共同点又有什么不同？像刚才一样，我们想用高阶函数来把变化的部分抽象出来。
fold :: (a -> b -> b) -> b -> [a] -> b
fold f z [] = z
fold f z (x:xs) = f x (fold f z xs)
注意到 fold 中把 [] 替换为 z，把 (:) 替换为 f，即
fold f z [a,b,c] == a `f` (b `f` (c `f` z))
从这个角度来看，你可能就知道如何推广 fold 到除了列表之外的其他数据结构上了。
下面，我们来用 fold 重写一下 sum'、product' 和 length'：
sum'' = fold (+) 0
product'' = fold (*) 1
length'' = fold addOne 0
where addOne _ s = 1 + s
当然 fold 已经在 Prelude 中了，叫做
foldr。
下面是一些 Prelude 中用 foldr 定义了的函数：
length :: [a] -> Intsum :: Num a => [a] -> aproduct :: Num a => [a] -> aand :: [Bool] -> Boolor :: [Bool] -> Boolany :: (a -> Bool) -> [a] -> Boolall :: (a -> Bool) -> [a] -> Bool
Prelude 还有一个
foldl,
表示 “从左向右” 折叠，即
foldr f z [a,b,c] == a `f` (b `f` (c `f` z))
foldl f z [a,b,c] == ((z `f` a) `f` b) `f` c
但一般情况下，你应该使用
Data.List 中的 foldl'
代替 foldl。它们做的事情是一样的，但前者更高效。
我们已经见过不少函数式编程的例子了。 为了更加适应这种编程的方式，我们现在来看看几个非常具有函数式风格的函数。
函数组合子
首先，我们还需要几个组合子：
(.) :: (b -> c) -> (a -> b) -> a -> c
(.) f g x = f (g x)
Prelude 中的 (.) 操作符即是函数的组合。
比如我们想要把列表中的每个元素加一然后乘以四，可以这样做：
add1Mul4 :: [Int] -> [Int]
add1Mul4 x = map ((*4) . (+1)) x
同时，我们也来看看 ($) 操作符，它的定义很简单：
($) :: (a -> b) -> a -> b
f $ x = f x
为什么需要这个？因为 ($) 是一个操作符，可以用来避免写很多括号。
例如，我们想得到列表中的偶数的个数的负数，可以这样写
negateNumEvens1 :: [Int] -> Int
negateNumEvens1 x = negate (length (filter even x))
或者这样
negateNumEvens2 :: [Int] -> Int
negateNumEvens2 x = negate $ length $ filter even x
少写很多括号呢！
Lambda
有时候我们需要创建匿名的函数，即lambda 表达式。用例子来说明，比如我们想重复列表中的所有字符串：
duplicate1 :: [String] -> [String]
duplicate1 = map dup
where dup x = x ++ x
单独给 dup 起个名字有点多余。其实，我们可以写成匿名函数：
duplicate2 :: [String] -> [String]
duplicate2 = map (\x -> x ++ x)
反斜线后面的变量名被绑定在了 -> 后面的表达式里。不过，长一些的函数还是起个名字最好。
还记得么，多参数函数的类型看起来有点儿奇怪，其中有很多“多余的”箭头？比如这个函数
f :: Int -> Int -> Int
f x y = 2*x + y
我曾经说过这其中是有优美深刻的原因的，现在终于是时间揭晓了：
其实所有的 Haskell 中的函数都只有一个参数。
什么？！上面这个函数 f 不是就有两个参数吗？
其实不是：它得到第一个参数（Int）然后返回了另一个函数（类型为 Int -> Int）；
而这个函数再得到另一个参数才返回最终的结果。
事实上我们可以把 f 的类型写成这样：
f' :: Int -> (Int -> Int)
f' x y = 2*x + y
需要指出的是，类型中的箭头是向右结合的，W -> X -> Y -> Z 等价于 W -> (X -> (Y -> Z))。
类型中最右顶层的的括号去掉也没有关系。
反过来，函数应用是左结合的。f 3 2 其实是 (f 3) 2 的简写。
这么说来我们之前说的 f 其实只需要一个参数然后返回另一个函数就合理了：
我们先把 f 应用在参数 3 上，得到一个类型为 Int -> Int 的函数，即一个对整数加六的函数。
然后把这个函数应用在参数 2 上，写作 (f 3) 2，最后得到一个整数。
因为函数应用是左结合的，所以我们可以把 (f 3) 2 缩写为 f 3 2，
看起来 f 就像一个“多参数”的函数一样。
“多参数”的 lambda
\x y z -> ...
其实只是
\x -> (\y -> (\z -> ...))
的语法糖。
同样，下面的定义
f x y z = ...
也是
f = \x -> (\y -> (\z -> ...)).
的语法糖。
把多参数函数表示为单参数并返回函数的函数叫做柯里化（currying），以英国数学和逻辑学家 Haskell Curry 命名。 （他的名字我们应该很熟悉，对，就是他。）柯里生于 1900 年逝于 1982 年，在宾州度过了他的大部分时光。 把多参数函数表示为单参数并返回函数的函数的想法其实首先是 Moses Schönfinkel 提出的， 所以可能更应该叫做 schönfinkeling。 柯里自己也指出这个想法来源于 schönfinkel，但是太晚了，别人早已经开始称其为 “currying” 了。
如果我们实在想表示一个有两个参数的函数，我们可以用一个元祖（tuple）来当参数。即
f'' :: (Int,Int) -> Int
f'' (x,y) = 2*x + y
这个函数可以看做有“两个”参数，尽管从某种意义上来说，它有的只是“一对”参数。
标准库里的 curry 和 uncurry 两个函数提供了这两种表达方式之间的转换：
curry :: ((a,b) -> c) -> a -> b -> c
curry f x y = f (x,y)
uncurry :: (a -> b -> c) -> (a,b) -> c
uncurry f (x,y) = f x y
当你有一个元祖对，想把它应用在一个函数上时，uncurry 就非常有用了。比如：
Prelude> uncurry (+) (2,3)
5
部分应用
Haskell 的函数都是已经柯里化了的，这使得部分应用变得非常简单。 部分应用的意思是指，我们把一个多参数的函数只应用到一部分参数上，得到一个可以应用剩余参数的函数。 但是我们刚刚已经见过了，Haskell 中从来没有多参数的函数！ 每一个函数都可以（并只能）被“部分应用”在它的第一个参数上，得到一个可以应用剩余参数的函数。
我们注意到在 Haskell 里部分应用除了第一个参数之外的参数就不那么容易了，除非使用中缀操作符。 我们已经见过，通过操作符域，中缀操作符可以被部分应用在它的两个参数任意一个上面。 所以在实际应用中这并不是什么限制了。 函数的参数的顺序也是有讲究的，要使得部分应用越方便越好：参数的顺序应服从“最小变化到最可能变化”。 即，不大会变的参数放在前面，时常变化的参数放在后面。
全麦编程
让我们来把刚学过的东西都放到一个例子里来，显示一下“全麦”风格的编程的威力。
比如如下定义的 foobar 函数：
foobar :: [Integer] -> Integer
foobar [] = 0
foobar (x:xs)
| x > 3 = (7*x + 2) + foobar xs
| otherwise = foobar xs
看起来足够直白，但这并不是最好的 Haskell 风格。问题出在：
- 同时做了太多事；
- 过于低层。
我们可以使用现有的几个递归模式，在整个输入上做增量变换，而不是考虑对每一个元素做什么。
下面是一个更为常见的 foobar 的实现：
foobar' :: [Integer] -> Integer
foobar' = sum . map ((+2) . (*7)) . filter (>3)
foobar' 被定义为三个函数串联的管道：
首先从列表中排除所有大于三的元素，然后对每个剩下的元素做算术操作，最后求和。
注意在上面的例子中，map 和 filter 都是被部分应用的。例如，filter 的类型为：
(a -> Bool) -> [a] -> [a]
应用在 (>3)(其类型为 Integer -> Bool)上，返回一个类型为 [Integer] -> [Integer] 的函数。
恰好能和另一个在 [Integer] 上的函数组合。
Point-free 风格
这种定义一个函数而不具名其参数 —— 与其在说定义函数是什么，不如说在定义函数做什么 —— 的风格常被称为 “point-free” 风格。
从上面的例子可以看出来，这种风格有时候非常优美。有些人可能会认为无论什么时候都应该使用 point-free 风格；
但是过于追求这种风格反而会造成巨大的困惑。
IRC 频道 #haskell 中的 lambdabot 有一个命令是 @pl，可以把函数转化为等价的 point-free 表达式；下面是一个例子：
@pl \f g x y -> f (x ++ g x) (g y)
join . ((flip . ((.) .)) .) . (. ap (++)) . (.)
这可一点也没有提升！
再看下面两个函数：
mumble = (`foldr` []) . ((:).)
grumble = zipWith ($) . repeat
你能明白他们在做什么吗？其实他们都等价于 map。
这些都是 point-free 风格过犹不及的例子。
所以有些人称之为 point-less（看不出要点）风格。