Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How can I fuse two maps over the same list?

Tags:

haskell

fusion

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").

like image 826
tibbe Avatar asked Sep 03 '12 04:09

tibbe


People also ask

How can I merge two maps?

concat() Alternatively, we can use Stream#concat() function to merge the maps together. This function can combine two different streams into one. As shown in the snippet, we are passed the streams of map1 and map2 to the concate() function and then collected the stream of their combined entry elements.

Can you combine two maps in Minecraft?

You can't merge maps. The only way to fully explore a map is to manually explore all the terrain shown on the map while holding that map.

How can you tell if two maps are the same?

We can compare two HashMap by comparing Entry with the equals() method of the Map returns true if the maps have the same key-value pairs that mean the same Entry.


2 Answers

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.

like image 139
Petr Avatar answered Sep 28 '22 08:09

Petr


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.

like image 40
tibbe Avatar answered Sep 28 '22 07:09

tibbe