14

xs我们可以在表达式中融合两个遍历列表

(map f xs, map g xs)

像这样

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

有没有关于自动执行这种融合的研究？

（如果一个返回的列表在另一个之前被消耗，那么这里就有创建空间泄漏的风险。我更感兴趣的是防止额外的遍历而xs不是节省空间。）

编辑：我实际上并不打算将融合应用到实际的内存中 Haskell 列表中，根据是否unzip可以与其消费者融合，这种转换可能没有意义。我有一个我知道unzip可以融合的设置（请参阅“FlumeJava：简单、高效的数据并行管道”）。

4

2 回答 2

4

也不是全自动的，但你可以给 GHC 一个这样的重写规则列表。请参阅7.14 重写规则和使用规则。然后编译器在编译时使用这些规则来优化你的程序。（请注意，编译器绝不会检查规则是否有意义。）

编辑：举一个这个特定问题的例子，我们可以写：

{-# 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。控制重写规则中发生的事情。

于 2012-09-03T07:35:00.717 回答
3

我设法找到了两个提到类似 fusion (un-)zip 的功能的资源，至少是简要的：

约瑟夫·斯文宁森。“用于累积参数和类似 Zip 功能的快捷方式融合” http://www.cse.chalmers.se/~josefs/publications/fusion.pdf

邓肯·库茨。“流融合：共归纳序列类型的实用快捷方式融合” https://community.haskell.org/~duncan/thesis.pdf

不过，这两种资源都没有明确提到这种“兄弟融合”。

于 2012-09-03T17:10:34.877 回答