如何在同一個列表中融合兩張地圖？

我們可以融合在列表xs兩次遍歷表達式如何在同一個列表中融合兩張地圖？

(map f xs, map g xs)

像這樣

unzip (map (\x -> (f x, g x)) xs)

是否有自動執行這種融合的任何reasearch？

（有一個風險在這裏創造一個空間泄漏如果返回的列表中的一個在另一個之前消耗掉，我更感興趣的是防止額外的穿越過xs比節省空間。）

編輯：實際上並不想將融合應用到實際的內存中的Haskell列表中，這種轉換可能沒有意義，取決於unzip是否可以與其消費者融合。我有一個設置，我知道unzip可以融合（請參閱「FlumeJava：簡單，高效的數據並行管道」）。

來源

2012-09-03 tibbe

不是自動的，但相當不錯：無論如何：http://squing.blogspot.com/2008/11/beautiful-folding.html –

除非這個結果與別的東西融合，否則創建對和解壓縮它們的開銷將會大於額外遍歷的成本。 – augustss

@augustss如果遍歷超過一個巨大的文件，則不會！我不打算將此應用於實際列表。 – tibbe

也不是完全自動的，但你可以給GHC一個這樣的重寫規則列表。見7.14 Rewrite rules和Using rules。然後編譯器在編譯時使用這些規則來優化你的程序。（請注意，在沒有辦法檢查的編譯器如果規則有任何意義。）

編輯：舉個例子對於這個特定的問題，我們可以這樣寫：

{-# OPTIONS_GHC -fenable-rewrite-rules -ddump-rule-firings -ddump-rule-rewrites #-} 

import Data.Char 

{-# RULES 
"map/zip" forall f g xs. (,) (map f xs) (map g xs) = unzip (map (\x -> (f x, g x)) xs) 
    #-} 

main :: IO() 
main = let x = "abCD" in 
     print $ (,) (map toUpper x) (map toLower x)

（頂級規則中的函數名稱是(,) :: a -> b -> (a, b)）。編譯時，您會看到規則是如何應用的。選項dump-rule-firings在應用規則時顯示消息，-ddump-rule-rewrites詳細顯示每個規則應用程序 - 請參閱7.14.6. Controlling what's going on in rewrite rules。

來源

2012-09-03 07:35:00

我不認爲我們可以編寫一個規則來匹配這些表達式。 GHC規則必須以函數名稱開頭。 – tibbe

我已經成功地找到兩個資源提到融合（未）壓縮功能一樣，至少簡要：

約瑟夫Svenningsson。「用於累積參數的快捷方式融合&拉鍊式功能」 http://www.cse.chalmers.se/~josefs/publications/fusion.pdf

Duncan Coutts。「Stream Fusion：合成序列類型的實用快捷方式融合」 https://community.haskell.org/~duncan/thesis.pdf

雖然資源沒有明確提及這種「兄弟融合」。

來源

2012-09-03 17:10:34 tibbe

我沒有看到這個演示文稿，但這裏是Josef關於[TupleFusion]的幻燈片（http://wiki.portal.chalmers.se/cse/uploads/FP/Josef_TupleFusion.pdf）。 – danr

[朝自動化tupling策略]（http://dl.acm.org/citation.cfm?id=154643）可能會很有趣。 –

如何在同一個列表中融合兩張地圖？

回答

相關問題