[Haskell-beginners] foldM efficiency

[Matthew Moppett]

I recently wrote the following code to solve a Project Euler problem:

coin :: Int -> Int -> [Int]
coin coinvalue stash = [stash, stash + coinvalue .. 200]
main = print . length . foldl (>>=) [0] $ map coin [200, 100, 50, 20, 10, 5, 2]


The program (correctly) works out how many ways there are to make up £2
from £2, £1, 50p, 20p, 10p, 5p, and 1p coins. Looking at the code, I
realised that (foldl (>>=) [0] . map) does a very similar job to foldM from
Control.Monad. So I tried rewriting the code as
follows:

import Control.Monad

coin :: Int -> Int -> [Int]
coin stash coinvalue = [stash, stash + coinvalue .. 200]
main = print . length $ foldM coin 0 [200, 100, 50, 20, 10, 5, 2]


This works, but it's about four times slower: it takes about 0.065 seconds
on my computer, while the first version takes about 0.017 seconds. To put
it another way, if I define foldM as follows:

foldM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a
foldM f x = foldl (>>=) (return x) . map (flip f)


... and use that definition instead of the standard Control.Monad version,
the code runs about four times faster. Here's the Control.Monad version
(copied from Hackage):

foldM             :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
foldM _ a []      =  return a
foldM f a (x:xs)  =  f a x >>= \fax -> foldM f fax xs


Why is my version so much faster here? And under what circumstances (if
any) could I expect the Control.Monad foldM to give better performance than
my version?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20140711/a964bb8c/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: FoldM.hs
Type: text/x-haskell
Size: 241 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/beginners/attachments/20140711/a964bb8c/attachment.hs>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: problem31a.hs
Type: text/x-haskell
Size: 169 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/beginners/attachments/20140711/a964bb8c/attachment-0001.hs>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: problem31b.hs
Type: text/x-haskell
Size: 175 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/beginners/attachments/20140711/a964bb8c/attachment-0002.hs>