[Haskell-cafe] Optimizing 'sequence'

[Don Stewart]

If you can demonstrate the required laziness/strictness properties
are identical, looks like a nice idea.

gracjanpolak:
> 
> 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
> 
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe