Maximum Segment Sum 的成長故事

前言

這篇我打算讓跟 program derivation 不熟的人也可以體會一下 squiggolists 是怎麼把 mss 的 linear-time, constant-space algorithm 變出來的。敘述有點冗贅，但稍微耐著性子應該不會很難讀（希望啦 XD），強烈建議讀一遍。對 derivation 有興趣的話，可以參考下面的懶人包：

• mss.lhs：包括可執行的 specification 和最終的 algorithm。
• mss.pdf：整個 derivation，需要一點 Algebra of Programming 的基礎。

如果看得懂 derivation，一定會感受到 functional program derivation 超強的表達能力 ─ 以下所有的解釋都可以收在 derivation 的符號裡面，更精簡也更準確。我會用 mss.pdf 第一頁 derivation 裡面的 premises 當作目前我們所在位置的提示。開始嘍！

definitions

怎麼算一個 list 的 maximum segment sum 呢？很簡單：先把這個 list 的所有 segments 產生出來，對每個 segment 算出元素和，然後取最大值。實作上，

1. 我們先找到 list 的所有 suffixes（例如 [1,2] 的所有 suffixes 是 [], [2], [1,2]），
2. 對於每一個 suffix 算出它的所有 prefixes（例如 [1,2] 的所有 prefixes 是 [], [1], [1,2]），
3. 把全部的 prefixes 放在一起後，
4. 算出每個 prefix 的和，
5. 最後取最大值。

naturality of concat

我們剛剛是先把每個 suffix 的 prefixes 放在一起之後再統一算出各個 prefix 的和。其實我們也可以在找到一個 suffix 的所有 prefixes 的時候就把這些 prefixes 個別的和算好，然後再把各個 suffix 對應的 prefix sums 收集起來。

claim: maximum . concat = maximum . map maximum

把每一個 suffix 的 prefix sums 收集起來是為了統一取最大值，但其實我們也可以在算出一個 suffix 的所有 prefix sums 後先取這些 prefix sums 的最大值，之後再對這些（與 suffixes 一一對應的）maximum prefix sums 取最大值。

map functor

現在的演算法是這樣的：

1. 找出 list 的所有 suffixes，
2. 對每個 suffix 算出全部的 prefixes，
3. 然後算出每一個 suffixes 的所有 prefix sums，
4. 在每一組 prefix sums 裡取最大值，
5. 最後在各組最大值裡面取最大值。

在取最後的最大值之前，我們都是對每一個 suffix 去算 prefixes、再對每一個 suffix 的 prefixes 算 prefix sums、再對每一個 suffix 的 prefix sums 取最大值，所以演算法也可以在找出 list 的所有 suffixes 之後對每一個 suffix 直接「算 prefixes、對每個 prefix 算出 prefix sum、取 maximum prefix sum」，三個動作一氣呵成，然後在「suffixes 對應的 maximum prefix sums」裡面取最大值。

first fusion

對於每一個 suffix 我們的最終目標是算出它的 maximum prefix sum，接下來的兩次融合會導出一個只做一次 traversal 的演算法計算這個值。第一次融合告訴我們，與其產出所有 prefixes 再算出每個 prefix 的和，不如直接產出所有的 prefix sums。算法是從 list 後面走回來：如果已經知道 xs 這個 list 的所有 prefix sums，那麼 x : xs（就是在 xs 前面接上元素 x）的 prefix sums 怎麼算呢？把 xs 的每一個 prefix sum 加上 x 就差不多是 x : xs 的 prefix sums，記得補上 empty prefix 的和 0 就行了。

second fusion

現在我們可以用一次 traversal 算出所有 prefix sums。第二次融合告訴我們，巡訪過程中可以順便算出 maximum prefix sum。算法是這樣的：既然我們只要 maximum prefix sum，何必在走過來的時候記住所有的 prefix sums 呢？假設 xs 的 prefix sums 是 s₁, s₂, ..., s_n，其中 s₁ 是最大的，那麼 x + s₁ 仍然是 {x + s_k}_{1 ≤ k ≤ n} 裡面最大的那一個，所以我們只要記住 xs 的 maximum prefix sum 就可以了。然而 x : xs 的 prefix sums 不只有 {x + s_k}_{1 ≤ k ≤ n}，還有一個 0，所以我們必須在 xs 的 maximum prefix sum 和 0 兩者當中取最大值，才是 x : xs 的 maximum prefix sum。

introducing scanr; third fusion

到這裡我們的演算法已經變成

1. 算出 list 的所有 suffixes，
2. 對每個 suffix 用一次 traversal 算出它的 maximum prefix sum，
3. 最後取最大值。

這種「對 list 所有 suffixes 做 traversal」的樣式叫做 scanr，而 scanr 其實也可以用一次 traversal 完成！如果我們已經有 xs 所有 suffixes 的 maximum prefix sums，我們也當然有 xs 本身的 maximum prefix sum，於是用和上面同樣的方法就可以算出 x : xs 的 maximum prefix sum。和原本那些 xs 所有 suffixes 的 maximum prefix sums 湊起來，就是 x : xs 所有 suffixes 的 maximum prefix sums。

split cancellation (backwards); fourth fusion

現在的演算法已經變得很簡單了：

1. 用一次 traversal 直接算出所有 suffixes 的 maximum prefix sums，
2. 然後在這些 maximum prefix sums 裡面取最大值。

看過這麼多次融合，一定猜到現在該做什麼了：把這兩步融合成單一次 traversal！計算 suffixes 的 maximum prefix sums 時，我們就不要把先前所有的 maximum prefix sums 都記住，只要記最大的那個就好 ─ 也就是標準的打擂台演算法。但是計算 x : xs 的 maximum prefix sum（也就是新的挑戰者）時我們需要 xs 的 maximum prefix sum，所以也要把它記住。如此一來，我們就得到標準的 linear-time, constant space algorithm，用一次 traversal 算出所有 suffixes 的 maximum prefix sums 當中的最大值。

結語

Functional program derivation 值得注意的一個特點是：每一步變換的結果都是一個新的演算法（當然解的是同一個問題），所以我們是在一開始顯然無誤的演算法裡面動手腳，逐漸改出最終的演算法。不得不說 squiggolists 選 mss 當作經典例子非常有道理，因為整個 derivation 都是 fold fusions（也就是 traversals 的合併），specification 拿起來拚命融就是了。做 derivation 的時候其實不用想這麼多具體的語意，只要操作語法和抽象語意（我保證這會簡單很多），程式就會像上面所描述地逐漸變換。Imperative programs 要做這種事情應該很難吧。

--
有整篇看完的人可以舉個手嗎？XD