problems with Control.Applicative
I really like the ideas behind Control.Applicative, but find it troublesome to use in practice. mainly, the minimalist choice of what to make class methods makes it very difficult to use for various applications. an example that is bugging me right now is that it is the _perfect_ fit for my frisby parser generator, however, I am unable to use it because the primitives 'pure' and 'fmap' and '<*>' which Control.Applicative is built on are not suitable low level primitives in practice (despite being sufficient in theory). 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. the rub is plain old fmap is almost never used, but all the useful things Control.Applicative provides are: in particular: (<$) :: Functor f => a -> f b -> f a (*>) :: Applicative f => f a -> f b -> f b (<*) :: Applicative f => f a -> f b -> f a optional :: Alternative f => f a -> f (Maybe a) some :: Alternative f => f a -> f [a] many :: Alternative f => f a -> f [a] (along with pure) are sufficient to encode pretty much every reasonable parser, and all of them have a special internal representation independent of 'fmap' it is rather disapointing that I can't make use of this library as it is in ghc when it is such a good fit for the application. Perhaps in the next revision we can move these (or a suitable subset) functions into the class? 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 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. Also, relying on rules means not being able to use polymorphic combinators built upon these primitives without taking special steps to ensure the rules can still fire. I really like the ideas behind Applicative,Traversable, and Foldable. but I feel these issues will unecesarrily hurt their utility. John -- John Meacham - ⑆repetae.net⑆john⑈
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?
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?
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 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 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 -- John Meacham - ⑆repetae.net⑆john⑈
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 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.
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⑈
John Meacham writes:
On Tue, Oct 17, 2006 at 11:09:00AM +0100, Ross Paterson wrote:
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
Would it help at all if liftA2 were part of the Applicative class? I've
usually defined Applicative like so,
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
(<*>) = liftA2 ($)
liftA2 f a b = fmap f a <*> b
(The pre 6.6 arrows package defined Control.Sequence in this fashion.)
Using that, you could define
instance Applicative P where
pure = P . Unit
liftA2 f (P a) (P b) = P $ PMap (uncurry f) (Then a b)
in which case <* and *> end up the same as <<- and ->>.
--
David Menendez
participants (3)
-
David Menendez -
John Meacham -
Ross Paterson