Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why is >>= faster than concatMap when they ought to be the same thing?

Last night, I was writing some recreational code, and at some point I replaced a concatMap with >>= and saw a ~10% speedup in my code.

I was under the impression the definition of >>= for [] was exactly concatMap, so I am a little confused.

like image 536
Emil Avatar asked Nov 06 '15 18:11

Emil


1 Answers

In base 4.8 (>>=) is implemented (see here) as:

xs >>= f = [y | x <- xs, y <- f x]

and concatMap is using a more complicated builder(source here)

concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
concatMap f xs = build (\c n -> foldr (\x b -> foldr c b (f x)) n xs)
like image 158
erdeszt Avatar answered Oct 21 '22 03:10

erdeszt