[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@home:~/some_faster> time ./Some1 +RTS -K100M
500000500000
real 0m2.318s
user 0m2.284s
sys 0m0.032s
gracjan@home:~/some_faster> time ./Some2
500000500000
real 0m0.652s
user 0m0.592s
sys 0m0.052s
--
Gracjan
_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Antoine Latter
>
> 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?
>
How does your version compare with the library version in the following tests:
test1 = do
(x:_) <- sequence [return 5, undefined]
return x
test2 = do
(x:_) <- sequence $ return 5 : undefined
return x
main = do
print $ runIdentity test1
print $ runIdentity test2
The function "runIdentity" is found in Control.Monad.Identity in the
mtl package.
(I haven't tried this code yet, so it may not really be syntactically
correct, but hopefully you get the idea.)
-Antoine
Don Stewart
are identical, looks like a nice idea.
gracjanpolak:
Janis Voigtlaender
> If you can demonstrate the required laziness/strictness properties
> are identical, looks like a nice idea.
I think they are not identical, as something along Antoine's second
example demonstrates.
--
Dr. Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:vo...@tcs.inf.tu-dresden.de
Gracjan Polak
>
> The function "runIdentity" is found in Control.Monad.Identity in the
> mtl package.
>
Thanks, I see it now! Laziness is not there!
But still... Identity is a bit special monad. What other monads need full
laziness in sequence? As far as I know IO is strict. What about lazy/strict
state monad?
Initially I spotted this possible optimization in context of monadic parser. I
am not really sure if I need this property there or not. How do I prove this to
myself?
Thanks to others who responded.
--
Gracjan
Janis Voigtlaender
> Initially I spotted this possible optimization in context of monadic parser. I
> am not really sure if I need this property there or not. How do I prove this to
> myself?
How about some QuickChecking in connection with the "Chasing bottoms"
library (http://citeseer.ist.psu.edu/704350.html)?
--
Dr. Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:vo...@tcs.inf.tu-dresden.de
_______________________________________________
Luke Palmer
> Antoine Latter <aslatter <at> gmail.com> writes:
>>
>> The function "runIdentity" is found in Control.Monad.Identity in the
>> mtl package.
>>
> laziness in sequence? As far as I know IO is strict. What about lazy/strict
> state monad?
A little formal reasoning reveals that sequence1 = sequence2 exactly
when (>>=) is strict in its left argument. There are four common
monads which are _not_: Identity, Reader, Writer, State (and RWS by
extension).
Luke
Chaddaï Fouché
> A little formal reasoning reveals that sequence1 = sequence2 exactly
> when (>>=) is strict in its left argument. There are four common
> monads which are _not_: Identity, Reader, Writer, State (and RWS by
> extension).
Still if that makes that much of a difference, maybe we could envision
putting a sequence' in the library ?
--
Jedaï
Gracjan Polak
> 2008/7/22 Luke Palmer <lrpalmer <at> gmail.com>:
> > A little formal reasoning reveals that sequence1 = sequence2 exactly
> > when (>>=) is strict in its left argument. There are four common
> > monads which are _not_: Identity, Reader, Writer, State (and RWS by
> > extension).
>
> Still if that makes that much of a difference, maybe we could envision
> putting a sequence' in the library ?
>
Yes, in my experiments this is to be or not to be. Stack space is limited.
Also processing time goes down by 800%, so it is a big deal sometimes.
Incomplete list of functions affected:
sequence
mapM
foldM
Text.ParserCombinators.Parsec.Combinator(many1,sepBy,endBy,manyTill)
Text.ParserCombinators.ReadP(many,many1,count,sepBy,endBy,manyTill)
..
As far as I know sequence could be specialized to IO monad and use my
transformation.
How do I reason if >>= for parsers is lazy in its first argument?
--
Gracjan
Janis Voigtlaender
> How do I reason if >>= for parsers is lazy in its first argument?
Well, to quote from the abstract of the paper I already mentioned
(http://citeseer.ist.psu.edu/704350.html): "By testing before proving we
avoid wasting time trying to prove statements that are not valid."
I think the library described in the paper, available here:
http://www.cs.nott.ac.uk/~nad/software/#Chasing%20Bottoms
has what you need. For example, you can check for isBottom, combine this
with random test case generation, and thus should be able to quickly
get an informed hypothesis about whether or not your >>= is lazy. For
then proving that hypothesis, the paper (and probably other papers it
cites) also provides some techniques that might be of use to you.
Ciao, Janis.
--
Dr. Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:vo...@tcs.inf.tu-dresden.de
_______________________________________________
Don Stewart
> Chaddaď Fouché <chaddai.fouche <at> gmail.com> writes:
> > 2008/7/22 Luke Palmer <lrpalmer <at> gmail.com>:
> > > A little formal reasoning reveals that sequence1 = sequence2 exactly
> > > when (>>=) is strict in its left argument. There are four common
> > > monads which are _not_: Identity, Reader, Writer, State (and RWS by
> > > extension).
> >
> > Still if that makes that much of a difference, maybe we could envision
> > putting a sequence' in the library ?
> >
>
> Yes, in my experiments this is to be or not to be. Stack space is limited.
> Also processing time goes down by 800%, so it is a big deal sometimes.
>
> Incomplete list of functions affected:
>
> sequence
> mapM
> foldM
> Text.ParserCombinators.Parsec.Combinator(many1,sepBy,endBy,manyTill)
> Text.ParserCombinators.ReadP(many,many1,count,sepBy,endBy,manyTill)
>
> As far as I know sequence could be specialized to IO monad and use my
> transformation.
>
> How do I reason if >>= for parsers is lazy in its first argument?
How about adding
Control.Monad.Strict
for the strict package?
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/strict
Andrew Coppin
> How about some QuickChecking in connection with the "Chasing bottoms"
> library (http://citeseer.ist.psu.edu/704350.html)?
Ah, finally a reference to what this curios phrase is actually about...!