Re: [Haskell-cafe] List Fusion of concatMap

1 Dec 2011

      Hi,

Am Donnerstag, den 01.12.2011, 21:44 +0100 schrieb Joachim Breitner:
...
Does ghc treat list comprehensions differently here?
I could answer this by looking at compiler/deSugar/DsListComp.lhs in the
GHC source:

        List comprehensions may be desugared in one of two ways:
        ``ordinary'' (as you would expect if you read SLPJ's book) and
        ``with foldr/build turned on'' (if you read Gill {\em et al.}'s
        paper on the subject).

(and indeed the translation depends on the flags) and later on:

        @dfListComp@ are the rules used with foldr/build turned on:

        TE[ e | ]            c n = c e n
        TE[ e | b , q ]      c n = if b then TE[ e | q ] c n else n
        TE[ e | p <- l , q ] c n = let 
                                        f = \ x b -> case x of
                                                          p -> TE[ e | q ] c b
                                                          _ -> b
                                   in
                                   foldr f n l

So I could manually rewrite func3 to:

func4 :: Int -> Bool
func4 k = any (>5) (build (\c n ->
    foldr (\x b -> case x of
            m -> 
                foldr (\x' b' -> case x' of 
                        i -> c i b'
                ) b [1..m]
    ) n [1..k]
    ))
{-# NOINLINE func4 #-}

and get identical core output. Having a case expression does not matter
in this case, because the code does all calculations completely with
unboxed integers anyways, so this can be written as follows, with still
identical core:

func5 :: Int -> Bool
func5 k = any (>5) (build (\c n ->
    foldr (\x b -> foldr c b [1..x]) n [1..k]
    ))
{-# NOINLINE func5 #-}

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?

Greetings,
Joachim

-- 
Joachim "nomeata" Breitner
  mail@joachim-breitner.de  |  nomeata@debian.org  |  GPG: 0x4743206C
  xmpp: nomeata@joachim-breitner.de | http://www.joachim-breitner.de/