[Haskell-cafe] >>= definition for list monad in ghc

Daniel Fischer daniel.is.fischer at googlemail.com
Mon May 16 22:26:18 CEST 2011

On Monday 16 May 2011 20:49:35, austin seipp wrote:
> As you can see, with the foldr definition, GHC is able to fuse the
> iteration of the input list with the generation of the result - note
> the 'GHC.Base.++' call with the first argument being a list from
> [x..x*2], and the second list to append being a recursive call. So it
> simplifies the code quite a bit - it doesn't really end up traversing
> a list, but instead generating a list only in this case, as it stores
> current iteration in a Int# and has the upper limit inlined into the
> case statement.
> I don't know why GHC doesn't have this rule by default, though.

Probably because it's not good. The core it generates for concatMap is 
better. With the driver

module Main (main) where

import ConcatMap
import System.Environment (getArgs)

main :: IO ()
main = do
    args <- getArgs
    let n = case args of
              (a:_) -> read a
              _     -> 12
    print $ sum $ test [1 .. n]

and different definitions of test, I get:

./useFoldr 10000 +RTS -s 
   3,415,002,336 bytes allocated in the heap
     232,459,348 bytes copied during GC

  MUT   time    1.55s  (  1.55s elapsed)
  GC    time    0.80s  (  0.80s elapsed)
  Total time    2.36s  (  2.35s elapsed)

(the same figures for concat (map k x) and for (x >>= k)) and

./useConcatMap 10000 +RTS -s 
   2,203,739,388 bytes allocated in the heap
         256,508 bytes copied during GC

  MUT   time    0.88s  (  0.88s elapsed)
  GC    time    0.03s  (  0.03s elapsed)
  Total time    0.91s  (  0.91s elapsed)

I'm still totally at a loss, why GHC generates different code for concatMap 
and foldr ((++) . k) [], though.

More information about the Haskell-Cafe mailing list