[Haskell-cafe] mapM is supralinear?

Ertugrul Soeylemez es at ertes.de
Wed Sep 7 16:20:03 CEST 2011


Travis Erdman <traviserdman at yahoo.com> wrote:

> The performance of mapM appears to be supralinear in the length of the
> list it is mapping on.  Does it need to be this way?  As a comparison,
> both mapM_ and map are linear in the length of the list.

It needs to be this way in most monads.  It's not a problem of mapM
itself, but of its definition in the particular monad.  In general it's
a bad idea to use mapM over IO.  For [] it will eat lots of memory
quickly and by its mere definition there is nothing you can do about
that.

mapM_ is linear, because it can throw away the results, so no
complicated accumulation occurs.  map is usually linear, because used
properly it will be optimized away leaving just a loop, which doesn't
produce any data structures in memory and is just run element by
element.


Greets,
Ertugrul


-- 
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/





More information about the Haskell-Cafe mailing list