problems with Control.Applicative
john at repetae.net
Tue Oct 17 06:51:39 EDT 2006
On Tue, Oct 17, 2006 at 11:09:00AM +0100, Ross Paterson wrote:
> On Tue, Oct 17, 2006 at 02:05:25AM -0700, John Meacham wrote:
> > a vital optimization involves finding common sub-parsers, for which it
> > performs a normalization pass and then a hash-consing to find common
> > parts.
> > 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 imagine you'd have a similar problem with pure -- perhaps you don't
> use it much. If seems the problem is that the Applicative interface
> encourages things like
> pure f <*> p <*> q <*> r
Yeah, that is basically the problem. all of the operations on
applicative are built on top of '<*>','fmap' and 'pure', all of which
hide their internal structure to some degree.
pure isn't so much of an issue because as you say, it doesn't come up
much. the most common case 'pure ()' has a special constructor in my
GADT so can be optimized well.
I basically avoid this issue by providing all sorts of useful
combinators that when used, preserve enough to allow optimization.
no one will write
pure const <*> a <*> b
when they could just write
a <* b
of course, this won't help if <* is implemented in terms of <*>.
> in which the left-associative <*> buries the function in the parser,
> while you'd prefer
> fmap (\ ((x,y),z) -> f x y z) (p <> q <> r)
> (where p <> q is equivalent to pure (,) <*> p <*> r)
> so presumably you'd want <> as a method in Applicative too.
I think the main ones would be (for frisby's use):
and more disturbingly, the definitions of 'some' and 'many' as given in
Control.Applicative lead to infinite loops!
John Meacham - ⑆repetae.net⑆john⑈
More information about the Libraries