[Haskell-cafe] Optimizing 'sequence'

[Gracjan Polak]

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
            where
              k m m' = do { x <- m; xs <- m'; return (x:xs) }

-- accumulator version
sequence2       :: Monad m => [m a] -> m [a]
sequence2 ms = sequence' [] ms
    where
        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
500000500000

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


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

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

--
Gracjan