Haskell 中没有 for 和 while 循环，而使用递归解决循环问题。
所谓递归，就是将一个大问题分解为两部分
- 先取出容易解决的一小部分进行处理
- 剩余部分作为同样的问题处理，但是规模变小了一点
- 问题的规模越来越小，直到遇到退出条件
这里的重点是，将剩余部分作为同样问题处理的时候，在语义上我们认为他已经解决了，可以将其当做一个确定的值参与到运算中
实作 Maximum
递归配合模式匹配和解构，非常容易实现
- 第一个模式是错误参数
- 第二个模式是退出条件
- 第三个模式将问题进行了分解
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
上面的代码用 where 定义了一个局部函数来比较当前值和剩余部分的大小，使用 max 函数可以进一步简化代码。
这里可以看出： max 函数将剩余问题当做了一个值参与了运算
maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:xs) = max x (maximum' xs)
几个常用递归函数
replicate
返回一个包含多个重复元素的列表, 如 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
take 函数
从一个列表中取出一定数量的元素。 如 take 3 [5,4,3,2,1], 得 [5,4,3]
take' :: (Num i, Ord i) => i -> [a] -> [a]
take' n _
| n <= 0 = []
take' _ [] = []
take' n (x:xs) = x : take' (n-1) xs
reverse 函数
反转一个 List
reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]
repeat 函数
取一个元素作参数, 回传一个仅包含该元素的无限 List
repeat' :: a -> [a]
repeat' x = x:repeat' x
zip 函数
取两个 List 作参数，将他们组合成一个序对的列表。zip [1,2,3] [2,3] 回传 [(1,2),(2,3)]
- 它会把较长的
List从中间断开, 以匹配较短的List - 用
zip处理一个List与空List会得一个空List，这是退出条件
zip' :: [a] -> [b] -> [(a,b)]
zip' _ [] = []
zip' [] _ = []
zip' (x:xs) (y:ys) = (x,y):zip' xs ys
elem 函数
它检测一个元素是否在一个 List 中
elem' :: (Eq a) => a -> [a] -> Bool
elem' a [] = False
elem' a (x:xs)
| a == x = True
| otherwise = a `elem'` xs
快速排序
快速排序是一个经典排序算法，非常快，其算法描述也非常“递归”
算法描述：
- 取出头部项（已解决的一小部分）
- 将所有小于等于头的项放在一组，并将其快速排序（即作为剩余问题解决）
- 将所有大于头的项放在一组，并将其快速排序（即作为剩余问题解决）
- 将小组、头、大组组合起来即可（即将各个部分看做已解决的值参与运算）
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
