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@joachim-breitner.de | nomeata@debian.org | GPG: 0x4743206C xmpp: nomeata@joachim-breitner.de | http://www.joachim-breitner.de/