[Haskell-cafe] Re: Optimizing 'sequence'
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? -- Gracjan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Optimizing 'sequence'
Gracjan Polak wrote: 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:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Optimizing 'sequence'
gracjanpolak: 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Optimizing 'sequence'
Janis Voigtlaender wrote: 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...! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Optimizing 'sequence'
Antoine Latter aslatter at gmail.com writes: 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Optimizing 'sequence'
Gracjan Polak wrote: 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:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Optimizing 'sequence'
On Tue, Jul 22, 2008 at 1:15 AM, Gracjan Polak [EMAIL PROTECTED] wrote: Antoine Latter aslatter at gmail.com writes: The function runIdentity is found in Control.Monad.Identity in the mtl package. 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? 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Optimizing 'sequence'
2008/7/22 Luke Palmer [EMAIL PROTECTED]: 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ï ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
