Haskell 基本语法（三）递归

发表于 | 分类于 | | 阅读次数:
字数统计: 2.7k | 阅读时长 ≈ 0:03

递归是一种定义函数的方式，在该方式下，函数的定义中调用了该函数本身。有点像俄罗斯套娃。

数学中的定义很多时候都会用到递归，比如 fibonacci 数列：

  • F(0) = 1
  • F(1) = 1
  • F(n) = F(n - 1) + F(n - 2)

于是有 F(3) = F(2) + F(1) = (F(1) + F(0)) + F(1) = 2。

递归函数的定义中，并不只是包含调用自身的代码，常常还需要非递归形式的定义，如上面的 F(0) = 1 和 F(1) = 1。这样的代码称作边缘条件（edge condition）。
边缘条件对于递归函数的终止至关重要。假如上面的 F(0) 和 F(1) 未定义，则任何一个输入都会导致函数无限调用自身，永远不会终止。

递归是 Haskell 中很重要的概念。不同于命令式的语言，在 Haskell 中需要定义计算本身是什么，而不是定义怎样一步步得出结果。

求最大值
1
2
3
4
5
6
7
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 函数（返回两个输入值中较大的那个）编写更短的形式：

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

当输入为 [2, 5, 1] 时，计算过程如下：
maximum' [2, 5, 1] -> max 2 (maximum' [5, 1]) -> max 2 (max 5 (maximum' [1])) -> max 2 (max 5 1) -> max 2 5 -> 5。

生成由固定数量的同一元素构成的列表
1
2
3
4
replicate' :: (Num i, Ord i) => i -> a -> [a]
replicate' n x
    | n <= 0    = []
    | otherwise = x:replicate' (n-1) x

如 replicate' 3 5 -> 5:(replicate' 2 5) -> 5:(5:(replicate' 1 5)) -> 5:(5:(5:(replicate' 0 5))) -> 5:(5:(5:[])) -> [5, 5, 5]。

取出列表中的前几个元素
1
2
3
4
5
take' :: (Num i, Ord i) => i -> [a] -> [a]  
take' n _
    | n <= 0   = []
take' _ []     = []
take' n (x:xs) = x : take' (n-1) xs

其中 take' n _ 和 take' _ [] 分别作为两种不同情况下的终止条件。
第一个模式 take' n _ 表示当 n 小于等于 0 时，不管输入的是什么样的列表都返回空列表 []。
可以作为如 take' 2 [1, 2, 3] 的终止条件。即前两个元素被取出并拼接成 [1, 2] 后 n 等于 0，满足第一个模式，递归终止。
第二个模式 take _ [] 表示当输入的列表是空列表时，不管 n 是多少都返回空列表。
可以作为如 take' 3 [1, 2] 的终止条件。即前两个元素被取出并拼接成 [1, 2] 后，n 为 1，但列表成为空列表，满足第二个模式，递归终止。
第三个模式 take' n (x:xs) 则用来定义从输入的列表头部逐个取出 n 个元素并拼接成新列表的递归逻辑。

reverse 的自定义实现
1
2
3
reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]
zip 的自定义实现
1
2
3
4
zip' :: [a] -> [b] -> [(a,b)]
zip' _ [] = []
zip' [] _ = []
zip' (x:xs) (y:ys) = (x,y):zip' xs ys
elem 的自定义实现（判断某个元素是否属于某个列表）
1
2
3
4
5
elem' :: (Eq a) => a -> [a] -> Bool
elem' a [] = False
elem' a (x:xs)
    | a == x    = True
    | otherwise = a `elem'` xs
快速排序
1
2
3
4
5
6
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
递归思维

递归函数的定义通常遵循如下模式：

  • 定义边缘条件（edge conditon）用于在特定条件下终止递归的执行
  • 取出部分元素执行特定操作，再调用递归函数本身处理剩余的元素

某个列表中所有元素之和等于该列表的第一个元素加上剩余的所有元素之和；某个列表的长度等于尾部（去除头部第一个元素）所有元素的长度加 1。

通常情况下，edge condition 就是令递归函数无实际意义的条件。对于列表来说，最常见的 edge condition 就是空列表。

参考资料

Learn You a Haskell for Great Good!