[Derivation] Plateau

這兩天在寫一個題目，要求一個list中最長的等價區段。也就是要找出list中最多有多少個相同且緊鄰的elements。

一開始我的作法很簡單。我先把list根據相同且相鄰的element分割成若干個list，再把全部放進一個list裡面。也就是[a,b,b,c,c]會變成[[a],[b,b],[c,c]]。然後再去計算其中每一個list的長度，最後在用foldr去取極大值，這樣就結束了。

     foldr max 0 ○ map length
= {map length = foldr (\x xs -> (length x) : xs) []}
     foldr max 0 ○ foldr (\x xs -> (length x) : xs) []
= {by fold-fusion}
      foldr (\(x:xs)->max (length x) xs) 0

      foldr max 0 ○ map length ○ refinement
= {see above reasoning}
      foldr (\(x:xs)->max (length x) xs) 0 ○ refinement

至此，問題就突然變成refinement要怎樣定義。一開始我的想法是先用fold去define refinement。也就有了：

cmb x xs =
  if x == ((head.head) xs)
     then (([x] ++ head xs):(tail xs))
     else ([x] : xs)

refinement = foldr cmb [[0]]

原式也因此變成了

plateau = foldr maxl 0 ○ foldr cmb [[0]]

然後這裡應該要在用一次fold fusion去把兩個fold fuse成一個。但是因為cmb有if-then-else，而fusing時我不太確定那個部份要怎樣去處理。所以這個方式就先按下不表。等之後精神比較健全的時候再來重心想一次。

接著,先回到refinement尚未定義的狀況。因為refinement的需求，我們知道refinement也可以用unfold來define。而且這樣整個式子就變成了fold ○ unfold。這樣一來就可以使用hylomorphism來消去中間產生的list of list。因此：

gen (x:xs) = < takeWhile (== x),dropWhile (== x) > (x:xs)

refinement = unfoldr (== 0) gen

plateau'
= {see above definition}
    foldr maxl 0 ○ unfoldr (== 0) gen
= {hylomorphism}
     if ((==0).length) a
     then 0
     else let (n,a') = (\(x:xs)->< takeWhile (== x), dropWhile (== x) > (x:xs)) a
         in (\x xs->max (length x) xs) n (plateau2 a')