[Haskell-cafe] mapM is supralinear?

[Travis Erdman]

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.


To wit:

travis at PW:~/Documents/insurer$ ghci
GHCi, version 7.0.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> :set +s
Prelude> :set +t
Prelude> :m Data.List Data.Maybe
Prelude Data.List Data.Maybe> foldl' (+) 0 $ fromJust $ mapM (\x -> Just x) [1..500000]
125000250000
it :: Integer
(2.23 secs, 112875864 bytes)
Prelude Data.List Data.Maybe> foldl' (+) 0 $ fromJust $ mapM (\x -> Just x) [1..1000000]
500000500000
it :: Integer
(6.86 secs, 214002204 bytes)
Prelude Data.List Data.Maybe> foldl' (+) 0 $ fromJust $ mapM (\x -> Just x) [1..2000000]
2000001000000
it :: Integer
(24.39 secs, 429299748 bytes)


Prelude Data.List Data.Maybe> foldl' (+) 0 $ map (\x -> x - 1) [1..1000000]
499999500000
it :: Integer
(0.77 secs, 171213436 bytes)
Prelude Data.List Data.Maybe> foldl' (+) 0 $ map (\x -> x - 1) [1..10000000]
49999995000000
it :: Integer
(7.42 secs, 1723399472 bytes)
Prelude Data.List Data.Maybe> foldl' (+) 0 $ map (\x -> x - 1) [1..40000000]
799999980000000
it :: Integer
(30.46 secs, 6894835952 bytes)



Prelude Data.List Data.Maybe> mapM_ (\x -> Just x) [1..1000000]
Just ()
it :: Maybe ()
(0.42 secs, 82761248 bytes)
Prelude Data.List Data.Maybe> mapM_ (\x -> Just x) [1..10000000]
Just ()
it :: Maybe ()
(3.87 secs, 808012660 bytes)
Prelude Data.List Data.Maybe> mapM_ (\x -> Just x) [1..100000000]
Just ()
it :: Maybe ()
(38.40 secs, 8054769564 bytes)
Prelude Data.List Data.Maybe>