a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)

[Luke Palmer]

On Fri, Apr 25, 2008 at 12:02 AM, Ben <midfield at gmail.com> wrote:
> Luke,
>
>  Thanks for the nice answer.  So maybe I'll give mapM3 the name mapM'
>  and put it in my personal library.

Except the answer was wrong.  I forgot the reverse in my
implementation, so that undefined we were seeing was just the last
element of the list.  But the conclusion is still true :-)

*Main> take 3 $ runIdentity $ mapM return (1:2:3:4:undefined)
[1,2,3]
*Main> take 3 $ runIdentity $ mapM3 return (1:2:3:4:undefined)
*** Exception: Prelude.undefined

>  But I'm still a bit curious about the performance profile of mapM.
>  The profiler is telling me they're allocating around the same amount
>  of memory, so I am not clear what is making it slow.  I am guessing it
>  has something to do with extra thunks due to laziness, but a 10x
>  slowdown?

Tail recursion can make a huge difference in strict settings: the
difference between a loop and recursion in C.

Luke