一場函數式思維模式的洗禮

寫在前面

以下語境都是 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 對象](/articles/箭頭函數-es6 筆記 6/#articleHeader8)，非要用的話，目前只有更醜的：

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)))
}

三。禮畢

好了，以後再談到兩個指針動來動去的話，函數式思維了解一下？怎麼找劃分點真的重要嗎？