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 ()
[EMAIL PROTECTED]:~/some_faster> time ./Some1 +RTS -K100M
500000500000
real 0m2.318s
user 0m2.284s
sys 0m0.032s
[EMAIL PROTECTED]:~/some_faster> time ./Some2
500000500000
real 0m0.652s
user 0m0.592s
sys 0m0.052s
--
Gracjan
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
