[Haskell-cafe] List Fusion of concatMap

[Joachim Breitner]

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>