[Haskell-cafe] List Fusion of concatMap
Joachim Breitner
mail at joachim-breitner.de
Thu Dec 1 23:20:55 CET 2011
Hi,
Am Donnerstag, den 01.12.2011, 22:16 +0100 schrieb Joachim Breitner:
> This would motivate the following definition for a fusionable concatMap,
> going via list comprehensions and their translation to ideal list fusion
> consumers/producers:
>
> concatMap f xs
> == [ y | x <- xs, y <- f x ]
> == build (\c n -> foldr (\x b -> foldr c b (f x)) n xs)
>
> And indeed, adding
> {-# RULES "myConcatMap" forall f xs . concatMap f xs = build (\c n -> foldr (\x b -> foldr c b (f x)) n xs) #-}
>
> to my file finally makes func1 behave the way I want it to, i.e. exactly
> the same core as the list comprehension variant, and no lists at all,
> only unboxed integers.
>
> Now I guess there is a reason why concatMap is not defined this way. But
> what is it?
I further tired to investigate where func2 (using "concat (map ..)")
goes wrong, after all, we have this rule for concat:
forall xs. concat xs = build (\c n -> foldr (\x y -> foldr c y x) n xs)
which is pretty close to what I am proposing for concatMap above. I used
"ghc -dverbose-core2core -ddump-rule-firings", but it seems that this
output is not complete; e.g. at some point,
RULES "eftInt" [~1] forall x y. eftInt x y = build (\ c n -> eftIntFB c n x y)
fires, but the output does not mention it. Anyway, I tried to
reconstruct what is happening in better readable terms:
We begin with func2 as given:
func2 k = any (>5) (concat (map (\m -> [1..m]) [1..k]))
rule "map"
func2 k = any (>5) (concat (build (\c n -> foldr (mapFB c (\m -> [1..m])) n [1..k])))
rule "concat"
func2 k = any (>5) (build (\c n -> foldr (\x y -> foldr c y x) n (build (\c n -> foldr (mapFB c (\m -> [1..m])) n [1..k]))))
rule "fold/build"
func2 k = any (>5) (build (\c n -> (\c n -> foldr (mapFB c (\m -> [1..m])) n [1..k]) (\x y -> foldr c y x) n))
rule "any/build"
func2 k = (\c n -> (\c n -> foldr (mapFB c (\m -> [1..m])) n [1..k]) (\x y -> foldr c y x) n) ((||) . (>5)) False
rule "eftInt"
func2 k = (\c n -> (\c n -> foldr (mapFB c (\m -> [1..m])) n (build (\c n -> eftIntFB c n 1 k))) (\x y -> foldr c y x) k) ((||) . (>5)) False
rule "fold/build"
func2 k = (\c n -> (\c n -> (\c n -> eftIntFB c n 1 k) (mapFB c (\m -> [1..m])) n) (\x y -> foldr c y x) n) ((||) . (>5)) False
beta-reduction
func2 k = eftIntFB (mapFB (\x y -> foldr ((||) . (>5)) y x) (\m -> [1..m])) False 1 k
At this point, if the definition of mapFB would be inlined, we
could continue successfully as follows. This is not what is
happening, but I am not sure why:
func2 k = eftIntFB (\x ys -> (\x y -> foldr ((||) . (>5)) y x) ((\m -> [1..m]) x) ys) False 1 k
beta-reduction
func2 k = eftIntFB (\m ys -> (foldr ((||) . (>5)) ys [1..m])) False 1 k
rule "eftInt"
func2 k = eftIntFB (\m ys -> (foldr ((||) . (>5)) ys (build (\c n -> eftIntFB c n 1 m)))) False 1 k
rule "fold/build"
func2 k = eftIntFB (\m ys -> (eftIntFB ((||) . (>5)) ys 1 m)) False 1 k
completely deforested code.
What do you think? Can the list fusion rules be improved so that they can catch these cases as well?
Greetings,
Joachim
--
Joachim "nomeata" Breitner
mail at joachim-breitner.de | nomeata at debian.org | GPG: 0x4743206C
xmpp: nomeata at joachim-breitner.de | http://www.joachim-breitner.de/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111201/47f63991/attachment.pgp>
More information about the Haskell-Cafe
mailing list