CODEWITHSUNDEEP
haskellfusion
tibbe
tibbe

Reputation: 9009

How can I fuse two maps over the same list?

We could fuse two traversals over the list xs in the expression

(map f xs, map g xs)

like so

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

Is there any reasearch on performing this kind of fusion automatically?

(There's a risk to create a space leak here if one of the returned lists is consumed before the other. I'm more interested in preventing the extra traversal over xs than saving space.)

Edit: I'm actually not looking to apply the fusion to actual in-memory Haskell lists, where this transformation might not make sense depending on if the unzip can be fused with its consumer(s). I have a setting where I know unzip can fuse (see "FlumeJava: easy, efficient data-parallel pipelines").

Upvotes: 14

Views: 367

Answers (2)

Petr
Petr

Reputation: 63359

Also not fully automatic, but you can give GHC a list of rewrite rules like that. See 7.14 Rewrite rules and Using rules. Then the compiler uses these rules to optimize your program when compiling. (Note that the compiler in no way checks if the rules make any sense.)

Edit: To give an example for this particular problem, we can write:

{-# 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)

(the top-level function name in the rule is (,) :: a -> b -> (a, b)). When compiling, you'll see how the rules are applied. Option dump-rule-firings shows a message when a rule is applied and -ddump-rule-rewrites displays each rule application in detail - see 7.14.6. Controlling what's going on in rewrite rules.

Upvotes: 4

tibbe
tibbe

Reputation: 9009

I've managed to find two resources that mentions fusion (un-)zip like functions, at least briefly:

Josef Svenningsson. "Shortcut Fusion for Accumulating Parameters & Zip-like Functions" http://www.cse.chalmers.se/~josefs/publications/fusion.pdf

Duncan Coutts. "Stream Fusion: Practical shortcut fusion for coinductive sequence types" https://community.haskell.org/~duncan/thesis.pdf

Neither resources mentions this kind of "sibling fusion" explicitly though.

Upvotes: 3

Related Questions