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): <* *> <> optional and more disturbingly, the definitions of 'some' and 'many' as given in Control.Applicative lead to infinite loops! John -- John Meacham - ⑆repetae.net⑆john⑈