14

xs式のリストで 2 つのトラバーサルを融合できます。

(map f xs, map g xs)

そのようです

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

この種の融合を自動的に実行することに関する研究はありますか?

(返されたリストの 1 つが他のリストの前に消費されると、ここでスペース リークが発生するリスクがあります。スペースを節約するよりも、余分なトラバーサルを防ぐことに関心がありますxs。)

unzip編集:実際には、融合を実際のメモリ内 Haskell リストに適用するつもりはありません。この変換は、消費者と融合できるかどうかによっては意味をなさない可能性があります。融合できることがわかっている設定があります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

フュージョン（un-）zipのような関数について言及している2つのリソースを、少なくとも簡単に見つけることができました。

ジョセフ・スヴェニングソン。「パラメータとZipのような関数を蓄積するためのショートカットフュージョン」 http://www.cse.chalmers.se/~josefs/publications/fusion.pdf

ダンカン・クーツ。「ストリームフュージョン：共誘導シーケンスタイプの実用的なショートカットフュージョン」 https://community.haskell.org/~duncan/thesis.pdf

ただし、どちらのリソースも、この種の「兄弟融合」については明示的に言及していません。

于 2012-09-03T17:10:34.877 に答える