写在前面
以下语境都是Haskell，没有循环结构，只能用递归来写作业
一.递归
先从一个简单的递归问题感受下函数式语言的语法魅力
求数组中的最大元素，可以这样做：
-- if-else
maximum' xs = if null xs then error "Empty list"
else if length xs == 1 then head xs
else max (head xs) (maximum' (tail xs))
数组中的最大元素就是首元与剩余元素最大值二者之中更大的那个
看起来不太漂亮，改改：
-- 模式匹配
maximum'' [] = error "Empty list"
maximum'' (x:xs) = if null xs then x
else max x (maximum' xs)
稍微有点感觉了，再改改：
-- Guard
maximum''' [] = error "Empty list"
maximum''' (x:xs)
| null xs = x
| otherwise = max x (maximum''' xs)
换上guard之后if-else消失了，似乎还不够清楚，再改改：
maximum'''' [] = error "Empty list"
maximum'''' [x] = x
maximum'''' (x:xs) = max x (maximum'''' xs)
现在语义相当自然了：
1.异常处理：空List没有最大值，报错
2.边界条件：单元素List的最大值就是该元素
3.递归定义：多元素List的最大值是首元与剩余元素最大值之间的较大值
递归算法本身就有很强的描述性，配合模式匹配能让语义更加清晰自然
二.函数式思维模式
好，现在我们被丢到了一个没有循环语句的世界，递归是唯一的出路
简单场景
先考虑一个简单的问题，如何实现length函数？输入一个List，输出其长度
length :: Foldable t => t a -> Int
按照习惯的命令式思维，遍历List计数搞定。那么，如何用递归描述List的长度（即提供其递归定义）？
length' [] = 0
length' (_:xs) = 1 + length' xs
非常地道的写法，语义如下：
1.边界条件：空List的长度为0
2.递归定义：非空List的长度是1加尾巴长度
隐约有那么点意思了，递归算法就是给出问题的解的递归定义，一般需要给个出口，即边界条件
有些问题本身就是递归定义的，比如斐波那契数列：
fib 0 = 0
fib 1 = 1
fib n
| n < 0 = error "Negative n is invalid"
| otherwise = fib (n - 1) + fib (n - 2)
而另一些问题的递归定义不那么明确，比如上面的length函数，似乎挨个数一遍更符合思维习惯，此时就需要给出其递归定义，进而得出递归算法
P.S.也有不留出口的死递归，例如repeat函数：
repeat' :: t -> [t]
repeat' x = x : (repeat' x)
如果支持限定长度，就是replicate函数：
replicate' times x
| times <= 0 = []
| otherwise = x : (replicate' (times - 1) x)
不很简单的场景
List操作中经常用take函数取出List的前n项：
take :: Int -> [a] -> [a]
以命令式的风格，自然是遍历收集前n项。但我们现在处于函数式语境，没有哪个数据结构能作为容器，没地儿放。所以结果自然是通过运算拼凑出来的新List：
take'' n xs
| n <= 0 || null xs = []
| otherwise = (head xs) : (take'' (n - 1) (tail xs))
语义还算明确：
1.边界条件：前0项或空List的take结果是空List
2.递归定义：前n项就是首项并上尾巴的前n-1项
但写法还不够地道：
take' _ [] = []
take' n _
| n <= 0 = []
take' n (x:xs) = x : take' (n - 1) xs
接下来尝试一个有趣的场景，实现reverse函数：
reverse :: [a] -> [a]
这次要求我们造出一个“颠覆性的“List，纯数据结构操作：
reverse' xs
| length xs <= 1 = xs
| otherwise = last xs : (reverse' (init xs))
上面这个函数说，List反转结果就是尾元并上其余元素的反转结果
再来一个操作数据结构的，比如zip：
zip :: [a] -> [b] -> [(a, b)]
把两个List整合成二元组List，长的部分要裁剪掉：
zip' [] _ = []
zip' _ [] = []
zip' (x:xs) (y:ys) = (x, y) : (zip' xs ys)
它说，两个List的整合结果是各自首元组成的二元组并上剩余部分的整合结果
鼓捣数据结构的递归似乎没什么意思了，来试个纯逻辑的，比如elem函数：
elem :: (Foldable t, Eq a) => a -> t a -> Bool
如何判断List是否包含指定元素？挨个比较一遍：
elem'' _ [] = False
elem'' n (x:xs) = x == n || (elem'' n xs)
首先空List里肯定没有，对于非空List，检查首元，不匹配就检查剩余元素。听起来不太像递归，重新组织一下语言：非空List的包含性就是首元的包含性或上其余元素的包含性
代码也重新组织一下，更地道一些的版本：
elem''' _ [] = False
elem''' n (x:xs)
| x == n = True
| otherwise = elem'' n xs
稍复杂的场景
这次面临第一个小关卡了，如何交换List中的两个元素？
swap :: Int -> Int -> [a] -> [a]
试试我们熟知的“套路”：
t = a
a = b
b = t
这在函数式环境似乎行不通，那么还有没有别的办法？当然有：
swap _ _ [] = []
swap i j xs
| i == j = xs
| i > j = swap j i xs
| otherwise = (take i xs) ++ [xs !! j] ++ (drop (i + 1) (take j xs)) ++ [xs !! i] ++ (drop (j + 1) xs)
上面这个函数说，一条线被2个点分成3段，List中两个元素交换的结果就是第一段并上第二个点，并上中间那段，再并上第一个点和最后一段
当然，这个问题与递归没什么关系，所以说递归是唯一的选择只是针对需要遍历的场景，不是所有问题都得用这把锤子钉两下
注意，其中drop a (take b xs)用来取出List中索引介于(a, b]之间的元素，更地道的写法是：
sublist _ _ [] = []
sublist a b xs
| a > b = []
| a == b = [xs !! a]
| otherwise = (drop a . take (b + 1)) xs
所以修改后的swap长这样子：
swap _ _ [] = []
swap i j xs
| i == j = xs
| i > j = swap j i xs
| otherwise = (take i xs) ++ [xs !! j] ++ (sublist (i + 1) (j - 1) xs) ++ [xs !! i] ++ (drop (j + 1) xs)
where sublist _ _ [] = []
sublist a b xs
| a > b = []
| a == b = [xs !! a]
| otherwise = (drop a . take (b + 1)) xs
追求更强的表达力的话，可以把剩余头尾2段也换成sublist
P.S.函数式语言追求小而美的组合，所以没有slice之类的东西，因为能够通过drop, take组合出来，专门提供一个就显得多余了
复杂场景
快速排序知道吧，写一个呗
快排的核心思路是：
男的站左边，女的站右边，老师站中间
好，开始排座位了。数学描述如下：
输入集合：A = {x | x <- a}
划分规则：
Left = {x | x <- a, x < pivot}
P = {pivot}
Right = {x | x<- a, x >= pivot}
递归定义：sort(A) = sort(Left) U P U sort(Right)
其中pivot是轴（一般选首元，追求稳定性的话，随机选个），即上面说的“老师”，左侧的元素都比他小，右侧的元素都比他大（或相等）
每趟快排的目标是找出pivot的最终位置，这个目的与冒泡/选择排序差不多：每趟选出一个最大/最小元素。解决问题的思路与归并排序类似：通过集合划分来缩减问题规模，归并排序先部分有序再让整体有序，而快排相当于先整体有序，再让各部分有序
我们所熟悉的经典快排算法是两个指针轮换移动，从左右两端向pivot的最终位置逼近，指针重合的位置就是本趟要找的划分点，把集合一分为二，再分别排序
好，那么，赶紧弄两个指针，开始移动吧
等一下，我们这会儿在函数式世界，集合操作再简单不过了，要什么指针
再看一眼快排的递归定义，不就是想知道哪些元素大于pivot，哪些元素小于pivot嘛，好说：
left (x:xs) = [a | a <- xs, a < x]
right (x:xs) = [a | a <- xs, a >= x]
两行List Comprehension搞定。所以快排的实现变得非常优雅：
quickSort' [] = []
quickSort' (x:xs) = (quickSort' left) ++ [x] ++ (quickSort' right)
where left = [a | a <- xs, a < x]
right = [a | a <- xs, a >= x]
那，如果非要用两个指针的经典方式实现呢？当然可以：
-- 2个指针，常用的寻找p最终位置的策略
-- p L ... H
quickSort'' [] = []
quickSort'' list@(x:xs) = (quickSort'' left) ++ [x] ++ (quickSort'' right)
where assign i v xs = (take i xs) ++ [v] ++ (drop (i + 1) xs)
pass p l h ltr xs
-- 把*l赋值为p，划分结束
| l >= h = l : (assign l p xs)
-- l右移
| ltr == True = if low < p then pass p (l + 1) h True xs
else pass p l (h - 1) False (assign h low xs)
-- r左移
| ltr == False = if high > p then pass p l (h - 1) False xs
else pass p (l + 1 ) h True (assign l high xs)
where low = xs !! l
high = xs !! h
nextList = pass x 0 (length list - 1) False list
(left, right) = let (x:xs) = nextList in ((take x xs), (drop (x + 1) xs))
里面用到的assign有点意思：
assign i v xs = (take i xs) ++ [v] ++ (drop (i + 1) xs)
数据不可变，所以又以这种“新奇”的方式来完成简单操作：1个点把一条线分成2段，抠掉这个点换上别的值，再把左右两段并上去
好，现在变态欲望得到满足了：我们证明了一个可行的算法与函数式/命令式环境无关，虽然多写了很多行。重新审视上面这两种思维模式的差异：
命令式：我跟你讲啊，弄两个指针，分别从左右两端逼近，这样做就能找出划分点，再对划分后的子集分别排序
函数式：排序就是把集合从轴一分为二，再对左右两边分别排序。其中，左边都小于轴，右边都大于（等于）轴
从描述问题的角度来看，函数式思维更专注于问题的解的定义，而命令式更关注如何说清楚每一个详细步骤。思维模式的差异大致是：前者先抽象后具体，后者先具体后抽象
当然，命令式语言中也可以由抽象及具体（先出算法骨架，再填充），所以说只是思维模式的差异。如同PowerPoint模板中的“主标题、副标题、列表项”带来的干扰一样，方便高效的循环结构在很大程度上影响了我们的思维模式：
这个问题，感觉得遍历，我们先写个循环，接下来再看循环体里该做什么
解决问题的方法与具体步骤同样重要，函数式的表达力就在于对方法的准确描述。听起来很熟悉，没错，小学6年级时，数学老师说：
这个问题用二元一次方程来解非常容易，用算术方法不太好想
从抽象到具体，是一种正向的思维过程，想要一步达到具体，则难的多
P.S.要不，来个JS的快速排序？：
function quickSort([x, ...xs]) {
return !arguments[0].length ?
[] :
quickSort(xs.filter(a => a < x)).concat([x]).concat(quickSort(xs.filter(a => a >= x)))
}
为什么!arguments[0].length看起来丑丑的，箭头函数不好吗？
不好，因为JS没有函数重载/模式匹配，也没有xxs@(x:xs)之类的保留原引用的方式，才出此下策。而箭头函数无法访问arguments对象，具体见4.关于arguments对象，非要用的话，目前只有更丑的：
const quickSort = xxs => {
if (!xxs.length) return []
let [x, ...xs] = xxs
return quickSort(xs.filter(a => a < x)).concat([x]).concat(quickSort(xs.filter(a => a >= x)))
}
三.礼毕
好了，以后再谈到两个指针动来动去的话，函数式思维了解一下？怎么找划分点真的重要吗？
