優化與摺疊

Question

我只是好奇，如果有任何（只有一階多態）優化與摺疊。

對於地圖，有森林砍伐：map g (map f ls) => map (g . f) ls和rev (map f ls) => rev_map f ls（在Ocaml更快）。

但摺疊是如此強大，它似乎無視任何優化。

Answer 1

顯而易見的：

fold_left f acc (List.map g li) => fold_left (fun acc x -> f acc (g x)) acc li 
fold_right f li acc => fold_left f acc li (* if (f,acc) is a monoid *) 

您可能感興趣的話題，「有香蕉，鏡頭，信封和鐵絲網的函數編程」經典論文。但要小心，它是技術性的，並有不可逾越的符號。

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125

編輯：我的第一個規則的第一個版本是錯誤的，編輯的感謝文森特 - hugot。

Answer 2

您可以在褶皺上使用砍伐森林。實際上，map/map融合是一個特例。

的竅門是通過一個特殊的build功能來代替列表構造：

build :: (forall b. (a -> b -> b) -> b -> b) -> [a] 
build g = g (:) [] 

現在使用的foldr

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr c n []  = n 
foldr c n (x:xs) = c x (foldr c n xs) 

我們有以下等價的標準定義：

foldr c n (build g) == g c n 

（其實這隻有在確定，但常見的情況。詳情請參閱"Correctness of short-cut fusion"）。

如果你寫你的列表產生功能使用foldr使用build和你的消費者（包括map），那麼上面的等式可以去除最中間的列表。 Haskell的列表解析被翻譯成build和foldr的組合。

這種方法的缺點是它不能處理左褶皺。 Stream Fusion可以解決這個問題。它將列表生成器和變換器表示爲流（coinductive數據類型，有點像迭代器）。上面的文章非常可讀，所以我建議看看。

gasche提到的「香蕉」論文更詳細地介紹了各種褶皺及其等價性。

最後，還有Bird和Moor的"Algebra of Programming"，其中提到了諸如combining two folds into one之類的轉換。

Answer 3

如果您有興趣進一步瞭解理論，我建議您閱讀一些關於catamorphisms,anamorphisms和hylomorphisms的內容。圍繞它的分類理論似乎有點可怕，但這個概念並不困難。

變形是函數消耗遞歸數據結構併產生某種類型的值。變形是賦予某些值的函數（一種種子）產生遞歸數據結構。特別是，在其他語言中提到的foldr和build是用於在列表上建立變形和變形的函數。但是，這個概念可以應用於基本上任何遞歸數據結構，例如不同種類的樹等。

現在，如果您建立具有變形的遞歸數據結構，然後將其與變形消耗相結合，就會得到所謂的「 hylomorphism。在這種情況下，你實際上不需要中間結構。你可以跳過創建並銷燬它。這通常被稱爲deforestation。

---

關於map：此功能有趣的是，這是一個既catamorphism 和的anamorphism：

• map消費清單，併產生一些;但也
• map產生一個列表，消耗的東西。

所以可以查看兩個映射map f . map g作爲anamorphism（map g）與catamorphism（map f）的組合物的組成，形成了hylomorphism。所以你知道可以通過不創建中間列表來優化（森林砍伐）。

要具體：你可以寫兩個map方式，一是使用foldr，另一個使用build：

mapAna :: (a -> b) -> [a] -> [b] 
mapAna f xs = build (mapAna' f xs) 

mapAna' :: (a -> b) -> [a] -> (b -> c -> c) -> c -> c 
mapAna' f []  cons nil = nil 
mapAna' f (x : xs) cons nil = (f x) `cons` (mapAna' f xs cons nil) 


mapCata :: (a -> b) -> [a] -> [b] 
mapCata f xs = foldr (\x ys -> f x : ys) [] xs 

和組成map f (map g zs)爲mapCata f (mapAna g zs)，這之後一些簡化和map (f . g)應用foldr c n (build g) == g c n結果。