problems with Control.Applicative

John Meacham john at
Tue Oct 17 05:05:25 EDT 2006

On Tue, Oct 17, 2006 at 09:23:24AM +0100, Ross Paterson wrote:
> On Mon, Oct 16, 2006 at 11:07:13PM -0700, John Meacham wrote:
> > The basic issue is that frisby relys on optimizing the parser before
> > executing it, so any static information that can be gleaned from the
> > built parser is very important to have available. however, the optimizer
> > has no way to "see through" an 'fmap' since the functional argument is
> > opaque as far as frisby is concerned.
> > [...]
> > note I don't really consider RULES appropriate here, knowing that the
> > optimizer will be able to see through these operations is vital for
> > writing a parser that works at all.
> I don't follow this part.  The argument of fmap is a semantic action,
> which is presumably independent of parsing decisions.  So without
> special versions of the operations you lose the ability to simplify
> composed actions, which will cost, but how does it prevent the parser
> from working at all?

a vital optimization involves finding common sub-parsers, for which it
performs a normalization pass and then a hash-consing to find common

Since there is no way to figure out whether two functions are equal, it
is forced to be pessamistic and assume they are distinct. If this occurs
too often, this creates a blow up in the final number of rules to the
point that the parser is no longer practical to use.

> > I would also like to see mapM_ as part of the class definition for
> > traversable. For many monads it makes the difference between linear and
> > constant space usage and space behavior of haskell programs is hard
> > enough to reason about without having to worry about certain rules
> > firing.
> Do you have an example where Data.Foldable.mapM_ uses linear space,
> and can this be avoided with a custom definition of Data.Foldable.foldr?

I ran into them before, I'll try to dig up an example that was causing
me trouble...

John Meacham - ⑆⑆john⑈

More information about the Libraries mailing list