一開始我的作法很簡單。我先把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')