一场函数式思维模式的洗礼

写在前面

以下语境都是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)))
}

三.礼毕

好了,以后再谈到两个指针动来动去的话,函数式思维了解一下?怎么找划分点真的重要吗?

参考资料

发表评论

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

*

code