Haskell学习笔记(二)——函数与递归

primes = filterPrime [2..]
    where filterPrime (p:xs) =
            p : filterPrime [x | x <- xs, x ´mod´ p /= 0]


五、Function

1.Pattern matching

Haskell的函数采用一种比较简洁易读的语法结构——模式匹配。它通过检查数据的特定结构来判断其是否匹配,并为每一种输入模式指定相应的函数定义。

我们看看阶乘函数的例子:

factorial :: (Integral a) => a -> a
factorial 0 = 1
factorial n = n * factorial (n - 1)

模式自上而下进行检查,如果匹配,则取相应的函数定义。第二行factorial 0 = 1仅匹配参数为 0 的情况,最后一行则会匹配一切的整数。

如果所有模式均不符合,就会报错,因此往往在最后放一个“万能匹配”来处理不可预料的输入情况。

模式匹配的精髓在于对参数的灵活处理,在其他语言如 Python 中,下面四个函数被称为“参数解构”:

- 将二维空间的两个向量相加的函数
addVectors :: (Num a) => (a, a) -> (a, a) -> (a, a)  
addVectors (x1, y1) (x2, y2) = (x1 + x2, y1 + y2)

- 以下三个函数分别返回三元组的第一、二、三个元素
first :: (a, b, c) -> a
first (x, _, _) = x

second :: (a, b, c) -> b
second (_, y, _) = y
 
third :: (a, b, c) -> c
third (_, _, z) = z

对 List 本身也可以使用模式匹配。你可以用 [] 或 : 来匹配它。因为[1,2,3]本质就是1:2:3:[]的语法糖。我们也可以使用前一种形式,像 x:xs 这样的模式可以将 List 的头部绑定为 x,尾部绑定为 xs。如果这 List 只有一个元素,那么xs 就是一个空 List。比如计算列表元素之和的 sum’:

sum' :: (Num a) => [a] -> a
sum' [] = 0
sum' (x:xs) = x + sum' xs

还有个东西叫做 as 模式,就是将一个名字和 @ 置于模式前,可以在按模式分割什么东西时仍保留对其整体的引用。如这个模式 xs@(x:y:ys),它会匹配出与x:y:ys对应的东西,同时你也可以方便地通过 xs 得到整个List,而不必在函数体中重复 x:y:ys。看下这个 quick and dirty 的例子:

capital :: String -> String
capital "" = "Empty string, oops!"
capital all@(x:xs) = "The first letter of " ++ all ++ " is " ++ [x]

ghci> capital "Sheriruth"
"The first letter of Sheriruth is S"

2.Guards

模式用来检查一个值是否合适并从中取值,而 guard 则用来检查一个值的某项属性是否为真。乍一听有点像是 if 语句,实际上也正是如此。不过处理多个条件分支时 guard 的可读性要高些,并且与模式匹配契合的很好。

比如我们现在用 guard 来写一个函数,它会依据你的身高来不同程度地羞辱你:

heightTell :: (RealFloat a) => a -> String
heightTell height
    | height <= 150.0 = "You're underheight, you!"
    | height <= 165.0 = "You're supposedly normal. Pffft, I bet you're ugly!"
    | height <= 180.0 = "You're really a tall man! Are you fatty?"
    | otherwise = "You're a giant, congratulations!"

guard 由跟在函数名及参数后面的竖线标志,通常他们都是靠右一个缩进排成一列。一个 guard 就是一个布尔表达式,如果为真,就使用其对应的函数体。如果为假,就送去见下一个 guard,如之继续。如果我们用 165.3 调用这个函数,它就会先检查它是否小于等于160.0,显然不是,于是见下一个guard。165.3 小于 170.0,因此通过了第二个 guard 的检查,就返回第二个字符串。

最后的那个 guard 往往都是 otherwise, 它的定义就是简单一个otherwise = True,捕获一切。 这与模式很相像,只是模式检查的是匹配,而它们检查的是布尔表达式。如果一个函数的所有 guard 都没有通过(而且没有提供 otherwise 作万能匹配),就转入下一模式。这便是 guard 与模式契合的地方。如果始终没有找到合适的 guard 或模式,就会发生一个错误。

另一个简单的例子:写个自己的 compare 函数。

myCompare :: (Ord a) => a -> a -> Ordering
a ´myCompare´ b
    | a > b     = GT
    | a == b    = EQ
    | otherwise = LT

ghci> 3 ´myCompare´ 2
GT

3.Where

上一节我们写了

heightTell :: (RealFloat a) => a -> String
heightTell height
    | height <= 150.0 = "You're underheight, you!"
    | height <= 165.0 = "You're supposedly normal. Pffft, I bet you're ugly!"
    | height <= 180.0 = "You're really a tall man! Are you fatty?"
    | otherwise = "You're a giant, congratulations!"

我们可以通过where来定义局部变量,将heightTell改写成如下形式:

heightTell :: (RealFloat a) => a -> String
heightTell height
    | height <= short  = "You're underheight, you!"
    | height <= normal = "You're supposedly normal. Pffft, I bet you're ugly!"
    | height <= high   = "You're really a tall man! Are you fatty?"
    | otherwise = "You're a giant, congratulations!"
    where short  = 150.0
          normal = 165.0
          high   = 180.0

函数在 where 绑定中定义的名字只对本函数可见,因此我们不必担心它会污染其他函数的命名空间。注意,其中的名字都是一列垂直排开,如果不这样规范,Haskell 就搞不清楚它们在哪个地方了。

where 绑定不会在多个模式中共享。如果需要在一个函数的多个模式中重复用到同一名字,就应该把它置于全局定义之中。

where 绑定也可以使用模式匹配!前面那段源代码可以改成:

...
where (short, normal, high) = (150.0, 165.0, 180.0)

where 绑定可以定义名字,也可以定义函数

where 绑定还可以一层套一层地来使用。有个常见的写法是,在定义一
个函数的时候也写几个辅助函数摆在 where 绑定中。而每个辅助函数也可以
通过 where 拥有各自的辅助函数。


4.Let

let 绑定与 where 绑定很相似。where 绑定是在函数模式底部定义名字,对包括所有 guard在内的整个模式可见。let 绑定则是个表达式,允许你在任何位置定义局部变量,而对不同的 guard 不可见。正如 Haskell 中所有赋值结构一样,let 绑定也可以使用模式匹配。

let 的格式为 let [bindings] in [expressions]。在 let 中绑定的
名字仅对 in 部分可见。let 里面定义的名字也得对齐到一列。下面是几个例子:

定义局部变量:

ghci> 4 * (let a = 9 in a + 1) + 2
42

也可以定义局部函数:

ghci> [let square x = x * x in (square 5, square 3, square 2)]
[(25,9,4)]

若要在一行中绑定多个名字,可以用分号将其分开。

ghci> (let a = 100; b = 200; c = 300 in a*b*c, "Hey there!")
(6000000,"Hey there!")

在 List Comprehension 中可以忽略 let 绑定的 in 部分,因为名字的可见性已经预先定义好了。同样,在 ghci 中 in 部分也可以省略,名字的定义就在整个交互中可见。


5.Case expressions

很多命令式语言 (C, C++, Java, etc.) 都提供了 case 语句。就是取一个变量,按照对变量的判断选择对应的源代码块。其中可能会存在一个万能匹配以处理未预料的情况。

Haskell 取了这一概念融合其中。实际上,模式匹配本质上不过就是 case 语句的语法糖而已。这两段源代码是完全等价的:

head' :: [a] -> a
head' [] = error "No head for empty lists!"
head' (x:_) = x
head' :: [a] -> a
head' xs = case xs of [] -> error "No head for empty lists!"
                      (x:_) -> x

看得出,case 表达式的语法十分简单:

case expression of pattern -> result
                   pattern -> result
                   pattern -> result
                   ...

expression 匹配合适的模式。第一个模式若匹配,就执行第一个区块的源代码;否则就接下去比对下一个模式。如果到最后依然没有匹配的模式,就会产生运行时错误

函数参数的模式匹配只能在定义函数时使用,而 case 表达式可以用在任何地方。例如:

describeList :: [a] -> String 
describeList xs = "The list is " ++ case xs of [] -> "empty."
                                               [x] -> "a singleton list."
                                               xs -> "a longer list."

同时给出相对应的模式匹配版本:

describeList :: [a] -> String
describeList xs = "The list is " ++ what xs
    where what [] = "empty."
          what [x] = "a singleton list."
          what xs = "a longer list."

六、Recursion

终于到了我们的递归函数了!如果你还不知道什么是递归,就读这个句子。哈哈!开个玩笑而已!

递归在 Haskell 中非常重要。命令式语言要求你提供求解的步骤,Haskell
则倾向于让你提供问题的描述。

1. 实现 Maximum

maximum 函数取一组可排序的 List(属于 Ord Typeclass)做参数,并返回其中的最大值。

想想,在命令式风格中这一函数该怎么实现。我们会设一个变量来存储当前的最大值,然后用循环遍历该 List,若存在比这个值更大的元素,则修改变量为这一元素的值。到最后,变量的值就是运算结果。

现在看看递归的思路如何:我们先定下一个边界条件,即处理单个元素的 List 时,返回该元素。如果该 List 的头部大于尾部的最大值,我们就可以假定较长的 List 的最大值就是它的头部。而尾部若存在比它更大的元素,它就是尾部的最大值。就这么简单!现在,我们在 Haskell 中实现它:

maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:xs)
    | x > maxTail = x
    | otherwise = maxTail
    where maxTail = maximum' xs

改用 max 函数会使源代码更加清晰。如果你还记得,max 函数取两个值做参数并返回其中较大的值。如下便是用 max 函数重写的 maximun’

maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:xs) = max x (maximum' xs)

太漂亮了!一个 List 的最大值就是它的首个元素与它尾部中最大值相
比较所得的结果,简明扼要。

2. 几个递归的例子

先实现下 replicate函数,它取一个 Int 值和一个元素做参数,返回一个包含多个重复元素的 List,如replicate 3 5返回[5, 5, 5]

replicate' :: (Num i, Ord i) => i -> a -> [a]
replicate' n x
    | n <= 0 = []
    | otherwise = x:replicate' (n-1) x

在这里我们使用了 guard 而非模式匹配,是因为这里做的是布尔判断。

*Note*: Num 不是 Ord 的子集, 表示数字不一定得拘泥于排序, 这就是在做加减法比较时要将 Num 与 Ord 类型约束区别开来的原因。

接下来实现 take函数,它可以从一个 List 取出一定数量的元素。如take 3 [5,4,3,2,1],得[5, 4, 3]。若要取零或负数个的话就会得到一个空List。同样,若是从一个空 List 中取值,它会得到一个空 List。注意,这儿有两个边界条件,写出来:

take' :: (Num i, Ord i) => i -> [a] -> [a]
take' n _
    | n <= 0 = []
take' _ [] = []
take' n (x:xs) = x : take' (n-1) xs

注意这里用了一个 guard 却没有指定 otherwise 部分,这就表示 n 若大于 0,会转入下一模式。

reverse 函数简单地反转一个 List,想一下它的边界条件!该怎样呢?想想……是空 List!空 List 的反转结果还是它自己。OK,接下来我们来实现它:

reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]

继续下去!

repeat 函数取一个元素作参数,返回一个仅包含该元素的无限 List。它的递回实现简单的很,看:

repeat' :: a -> [a]
repeat' x = x:repeat' x

Haskell 支持无限 List,所以我们的递归就不必添加边界条件。这样一来,它可以对某值计算个没完,也可以产生一个无限的数据结构,如无限List。

无限 List 的好处就在于我们可以在任意位置将它断开。调用 repeat 3 会得到一个以 3 为头部并无限数量的 3 为尾部的 List,可以说 repeat 3 运行起来就是 3:repeat 3,然后 3:3:3:3 等等。若执行 repeat 3,那它的运算永远都不会停止。而 take 5 (repeat 3) 就可以得到 5 个 3,与 replicate 5 3 差不多。

zip 取两个 List 作参数并将其捆在一起。zip [1,2,3] [2,3] 返回
[(1, 2), (2, 3)],它会把较长的 List 从中间断开,以匹配较短的 List。

zip' :: [a] -> [b] -> [(a,b)]
zip' _ [] = []
zip' [] _ = []
zip' (x:xs) (y:ys) = (x,y):zip' xs ys

再实现一个标准库函数 —— elem!它取一个元素与一个 List 作参数,并检测该元素是否包含于此 List。

elem' :: (Eq a) => a -> [a] -> Bool
elem' a [] = False
elem' a (x:xs)
    | a == x    = True
    | otherwise = a ´elem'´ xs

这里的模式匹配也可以写成中缀形式:

elem' :: (Eq a) => a -> [a] -> Bool
a ´elem'´ [] = False
a ´elem'´ (x:xs)
    | a == x = True
    | otherwise = a ´elem'´ xs

3.Quicksort

假定我们有一个可排序的 List,其中元素的类型为 Ord Typeclass 的成员。现在我们要给它排序!有个排序算法非常的酷,就是快速排序 (quicksort)。 尽管它在命令式语言中也不过 10 来行,但在 Haskell下边要更短,更漂亮。我们在这里也实现一下。或许会显得很俗气,因为每个人都用它来展示 Haskell 究竟有多优雅!

它的类型声明应为 quicksort :: (Ord a) => [a] -> [a],没什么奇怪的。

边界条件呢?如料,空 List。排过序的空 List 还是空 List。

接下来便是算法的定义:排过序的 List 就是令所有小于等于头部的元素在先 (它们已经排过了序),后跟大于头部的元素 (它们同样已经排过了序)。为方便我们把 head 设为 pivot。注意定义中有两次排序,所以就得递归两次!同时也需要注意算法定义的动词为 “是” 什么而非 “做” 这个,“做” 那个,再 “做” 那个……这便是函数式编程之美!

如何才能从 List 中取得比头部小的那些元素呢?List Comprehension。好,一起就绪,动手写出这个函数!

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smallerSorted = quicksort [a | a <- xs, a <= x]
        biggerSorted = quicksort [a | a <- xs, a > x]
    in smallerSorted ++ [x] ++ biggerSorted

小小地测试一下:

ghci> quicksort [10,2,5,3,1,6,7,4,2,3,4,8,9]
[1,2,2,3,3,4,4,5,6,7,8,9,10]
ghci> quicksort "the quick brown fox jumps over the lazy dog"
"        abcdeeefghhijklmnoooopqrrsttuuvwxyz"

Bingo!

此条目发表在函数式语言分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注