[Haskell-cafe] Optimizing 'sequence'

Gracjan Polak gracjanpolak at gmail.com
Mon Jul 21 14:54:09 EDT 2008

Hi all,

On the other day I noticed that we could optimize 'sequence' more.
I needed it for my monadic parser. Below is my small experiment.
Sequence from standard library needs 2.3s to finish (and additional
stack space), my version uses only 0.65s and default stack.

Is my version better or am I missing something obvious?

-- standard
sequence1       :: Monad m => [m a] -> m [a]
sequence1 ms = foldr k (return []) ms
              k m m' = do { x <- m; xs <- m'; return (x:xs) }

-- accumulator version
sequence2       :: Monad m => [m a] -> m [a]
sequence2 ms = sequence' [] ms
        sequence' vs [] = return (reverse vs)
        sequence' vs (m:ms) = m >>= (\v -> sequence' (v:vs) ms)

main = do
    let l = map return [1..1000000]
    w <- sequence1 l
    print (sum w)
    return ()

gracjan at home:~/some_faster> time ./Some1 +RTS -K100M

real    0m2.318s
user    0m2.284s
sys     0m0.032s

gracjan at home:~/some_faster> time ./Some2

real    0m0.652s
user    0m0.592s
sys     0m0.052s


More information about the Haskell-Cafe mailing list