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?
