一场函数式思维模式的洗礼
写在前面
以下语境都是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)))
}三.礼毕
好了，以后再谈到两个指针动来动去的话，函数式思维了解一下？怎么找划分点真的重要吗？
参考资料
- Debugging
- Abstract data type
- Destructuring assignment in function call while preserving the object [duplicate]