如何在同一个列表中融合两张地图？

我们可以融合在列表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）可能会很有趣。 –

如何在同一个列表中融合两张地图？

回答

相关问题