7 區段問題

7.2 最長高原問題

如果一個區段的每個元素都相等，我們稱之為一個「高原(plateau)」。 本節考慮這個問題：給一個串列，找出其中最長的高原的長度。 例如當輸入為 [2,3,3,2,2,2,1,6,6] 時，輸出應為 3 --- 即最長的高原 [2,2,2] 的長度。 以下是本問題的一種可能的規格寫法：

lp :: List Int -> Int
lp = maximum . map length . filter plateau . segmentsP

其中 segmentsP 算出所有的區段，plateau 判斷一個區段是否為高原。 過濾出所有的高原後，我們計算每個高原的長度，然後找出最大值。 函數 lp 與 plateau 可以有更通用的型別 Eq a => List a -> Int, Eq a => List a -> Bool.

函數 segmentsP 和 segments 類似，其定義為：

segmentsP :: List a -> List (ListP a)
segmentsP = concat . map initsP . tailsP

函數 initsP 與 tailsP 則與 inits 與 tails 類似，但只傳回非空的前後段，定義如下：

initsP :: List a -> List (ListP a)
initsP []      = []
initsP (x:xs)  = [x] : map (x:) (initsP xs) {-"~,"-}


tailsP :: List a -> List (ListP a)
tailsP []      = []
tailsP (x:xs)  = (x:xs) : tailsP xs

以上三個函數的回傳型別都是 List (ListP a) --- 每個傳回的前/後/區段都是非空的，但並非每個串列都有非空的前/後/區段。 函數 lp 仍可接受空串列作為輸入，但（我們等下將看到）在規格中使用 segmentsP 將帶來不少方便。 我們也可使用 segments 定最長平原問題的規格，只是會增加一些不利於講解的細節。

函數 plateau 可定義如下：

plateau :: ListP Int -> Bool
plateau [x]       = True
plateau (x:y:xs)  = x == y ⋀ plateau (y:xs)

由於輸入是非空串列，plateau 的定義中考慮的是「有一個元素」和「有兩個以上元素」的兩種情況。

區段問題不傳回區段？

為何我們在最大區段和問題中只傳回最大區段的和、在最長高原問題中只傳回長度，而不傳回該區段本身呢？

\quad 這是許多演算法題目常見的簡化：當真正的問題是尋找「使得某值最大的聚合資料結構」時，我們常只要求解題者傳回該值，而不是整個聚合資料結構。如此做的好處之一是讓我們能暫時忽略「如何組出需傳回的資料結構」的細節，更專注在問題本身。這使得問題的規格與推導過程都簡單許多。

\quad 如果我們真的需要整個區段，我們總能將前述的簡單版程式擴充為傳回資料結構的程式。讀者不妨試試能否將第 頁的 mpsAll 改寫為型別為 List Int -> List (Int × List Int) 的程式 --- 對每個後段，計算其最佳前段和，以及該前段。您會發現程式結構並沒有改變，只是多了些繁瑣的細節。

\quad 另一個理由是：具有最大和的區段可能不只一個。在函數程式推導之中，如果我們要傳回區段，由於規格也是函數，我們似乎必須在規格中就決定傳回哪一個。若希望規格是「傳回任一個具有最大和的區段」，我們會需要更多機制，例如使用關係(relation)或使用單子。

前段-後段分解   和最大區段和問題一樣，我們先嘗試把這個區段問題分解為「對每個後段，計算最佳前段」：

      maximum . map length . filter plateau . segmentsP
 ===  maximum . map length . filter plateau . concat . map initsP . tailsP
 ===     {- 因 filter p . concat = concat . map (filter p) -}
      maximum . map length . concat . map (filter plateau . initsP) . tailsP
 ===     {- 因  map f . concat = concat . map (map f), map 融合 -}
      maximum . concat . map (map length . filter plateau . initsP) . tailsP
 ===     {- 因 maximum . concat = maximum . map maximum, map 融合 -}
      maximum . map (maximum . map length . filter plateau . initsP) . tailsP

嘗試使用掃描引理   下一步：我們把 maximum . map length . filter plateau . initsP 簡寫為 lpp， 並嘗試將它寫成 ([RefUndefined]) 的形式，以便使用掃描引理。演算如下：

      (maximum . map length . filter plateau . initsP $ (x:xs))
 ===  (maximum . map length . filter plateau $ [x] : map (x:) (initsP xs))
 ===    {- filter 之定義，plateau [x] = True -}
      maximum (1 : map length (filter plateau (map (x:) (initsP xs))))
 ===  1 ↑ maximum (map length (filter plateau (map (x:) (initsP xs))))

演算至此的問題是：如何把 map (x:) 提出來呢？ 定理2.4 允許我們把 map 搬到 filter 的左邊：

 filter p . map f = map f . filter (p . f)

至於 plateau . (x:) 能否再化簡？觀察 plateau 定義的第二個子句：

plateau (x:y:xs)  = x == y ⋀ plateau (y:xs)

寫成函數組合的形式便是：

plateau . (x:) = ((x ==) . head) ⋀: plateau

其中 (⋀:) 為「提升成函數版」的 (⋀), 定義為

(⋀:) :: (a -> Bool) -> (a -> Bool) -> a -> Bool
(f ⋀: g) x = f x ⋀ g x

函數 (⋀) :: Bool -> Bool -> Bool 拿兩個布林值、算出一個新布林值，(⋀:) 則拿兩個函數 f, g :: a -> Bool，組合成另一個型別為 a -> Bool 的函數，其結果是 f 與 g 之傳回值的合取。函數 filter 與 (⋀:) 有如下的性質：

  filter (p ⋀: q) & = filter p . filter q     (7.3 )

有了以上眾多性質，我們演算如下：

      filter plateau . map (x:)
 ===    {- 定理 2.4 -}
      map (x:) . filter (plateau . (x:))
 ===    {- plateau 之定義 -}
      map (x:) . filter (((x ==) . head) ⋀: plateau)
 ===    {- 因 \eqref{eq:filter-conjunct}: filter (p ⋀: q) = filter p . filter q -}
      map (x:) . filter plateau . filter ((x ==) . head)

現在整個式子成為 1 ↑ (maximum . map (length . (x:)) . filter plateau . filter ((x ==) . head) . initsP) $ xs.

把 map (x:) 往左搬之後，式子的右邊出現了 filter ((x ==) . head) (initsP xs) --- 產生所有 xs 的非空前段，取出第一個元素為 x 的。但讀者們可能立刻發現：initsP 傳回的每個前段的第一個元素都是一樣的！也就是說我們有以下性質。

考慮非空前段的好處在這兒可看出：head 對非空串列才有值。

回到 lpp，我們可繼續推導如下：

      lpp (x : xs)
 ===   {- 前述演算, map 融合 -}
      1 ↑  (maximum . map (length . (x:)) . filter plateau .
                  filter ((x ==) . head) . initsP $ (x : xs))
 ===   {- 因 \eqref{eq:initsP-heads} -}
      1 ↑  (maximum . map (length . (x:)) . filter plateau $
                  if x == head xs then initsP xs else [])
 ===   {- \eqref{eq:fn-if-distribute}: 函數分配進 if -}
      if x == head xs
        then 1 ↑  (maximum . map (length . (x:)) . filter plateau . initsP $ xs)
        else 1 ↑ (maximum . map (length . (x:)) . filter plateau $ [])
 ===   {- length . (x:) = (1+) . length, 及其他化簡 -}
     if x == head xs
        then 1 + (maximum . map length . filter plateau . initsP $ xs)
        else 1
 ===   {- lpp 之定義 -}
     if x == head xs then 1 + lpp xs else 1

由此我們得到

lpp [x]     = 1
lpp (x:xs)  = if x == head xs then 1 + lpp xs else 1

然而，我們雖為 lpp 推導出了一個歸納定義，該定義並不符合 ([RefUndefined])！ 後者要求 lpp 的右手邊必須是 x ⊕ lpp xs 的形式 --- 在 lpp xs 之外不能有其他的 xs, 而上述的 lpp 右手邊多了一個 head xs.

這時組對的技巧又派上用場了。定義：

lpph xs = (lpp xs, head xs)

我們可推導出

lpph [x]     = (1, x)
lpph (x:xs)  = (if x == y then 1 + n else 1, x) 
   where (n,y) = lpph xs

該函數符合 ([RefUndefined]) 的形式，其中 e = (1,x), x ⊕ (y,n) = (if x == y then 1 + n else 1, x).

總結   綜合目前為止的推導，函數 lpp 的推導大架構如下：

      lpp
 ===    {- 前段-後段分解 -}
      maximum . map (maximum . map length . filter plateau . initsP) . tailsP
 ===    {- 前述演算：尋找歸納定義 -}
      maximum . map lpp . tailsP
 ===    {- 因 lpp = fst . lpph  -}
      maximum . map (fst . lpph) . tailsP
 ===    {- 掃描引理 -}
      maximum . map fst . lpphAll

其中 lpphAll 的定義如下：

lpphAll [x]     = [(1,x)]
lpphAll (x:xs)  = (if x == y then 1 + n else 1, x) : (n,y) : ys 
  where ((n,y) : ys) = lpphAll xs

這是一個使用線性時間、線性空間的演算法。