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

[Daniel Fischer]

On Monday 16 May 2011 20:49:35, austin seipp wrote:
> Looking at the Core for an utterly trivial example (test x = concatMap
> k x where k i = [i..i*2]), the foldr definition seems to cause a
> little extra optimization rules to fire, but the result seems pretty
> big. The definition using concatMap results in core like this:
> 

Hmm, something seems to be amiss, writing

test :: [Int] -> [Int]
test x = concat (map k x)
  where
    k :: Int -> [Int]
    k i = [i .. 2*i]

the core I get is

Rec {
ConcatMap.test_go [Occ=LoopBreaker]
  :: [GHC.Types.Int] -> [GHC.Types.Int]
[GblId, Arity=1, Caf=NoCafRefs, Str=DmdType S]
ConcatMap.test_go =
  \ (ds_aoS :: [GHC.Types.Int]) ->
    case ds_aoS of _ {
      [] -> GHC.Types.[] @ GHC.Types.Int;
      : y_aoX ys_aoY ->
        case y_aoX of _ { GHC.Types.I# x_aom ->
        GHC.Base.++
          @ GHC.Types.Int
          (GHC.Enum.eftInt x_aom (GHC.Prim.*# 2 x_aom))
          (ConcatMap.test_go ys_aoY)
        }
    }
end Rec }

which is identical to the core I get for foldr ((++) . k) [].
Writing concatMap, I get the larger core (I'm not sure which one's better, 
the concatMap core uses only (:) to build the result, that might make up 
for the larger code).

But, as Felipe noted, concatMap is defined as

-- | Map a function over a list and concatenate the results.
concatMap               :: (a -> [b]) -> [a] -> [b]
concatMap f             =  foldr ((++) . f) []

in GHC.List. There are no RULES or other pragmas involving concatMap either 
there or in Data.List. In the absence of such pragmas, I would expect 
concatMap to be inlined and thus to yield exactly the same core as
foldr ((++) . f) []