proposal #3335: make some Applicative functions into methods, and split off Data.Functor

[Edward Kmett]

On Wed, Aug 19, 2009 at 4:21 PM, Ross Paterson <ross at soi.city.ac.uk> wrote:

> On Wed, Aug 19, 2009 at 01:04:13PM -0400, Edward Kmett wrote:
> > (*>) and (<*) could be used to apply recognizing parsers for the
> > discarded half.  This makes a huge gain for uu-parsinglib.
> > uu-parsinglib's P_m monad could be extended just as it has done with
> > P_f and P_h to also wrap its existing R monad, which would let it
> > apply the parser as a recognizer efficiently.
> >
> > And for parsimony it allows me to treat that side of the alternative
> > grammar as a right seminearring ignoring the argument, this increases
> > sharing opportunities for my grammar fragments, because pure nodes in
> > recognizers can be treated as epsilons in the grammar and safely elided.
>
> code?


The parsimony case is a bit drastic to post here, because I'd have to
basically post the whole library and I haven't released it yet, or rewritten
it to accomodate these extra Applicative actions.

However, I can try to do justice to how uu-parsinglib could use the new
members. It currently has several parsers, which have types i'll abridge
here.

newtype  P_h    st  a =  P_h  (forall r . (a  -> st -> Steps r)  -> st ->
Steps r)
newtype  P_f st a  = P_f (forall r . (st -> Steps   r) -> st -> Steps   (a,
r))
newtype  R st a  = R (forall r . (st -> Steps   r) -> st -> Steps r)
newtype P_m state a = P_m (P_h  state a, P_f state a)

It uses an 'ExtApplicative' class to let it mix recognizers (R's) with other
parsers when you will just be discarding the recognized branch of the
result. Note P_f and R are both Applicative, not Monadic.

I'll just handle (<*) to avoid clutter below.

 class  Applicative p => ExtApplicative p where
  (<<*)      ::  p  a -> R (State p) b   -> p  a

instance ExtApplicative (P_h st)  where
  P_h p <<* R r     = P_h ( p. (r.))
instance ExtApplicative (P_f st) where
  P_f p <<* R r     = P_f (\ k st -> p (r k) st)

R just discards its phantom type argument. So it is trivially a Functor.

instance Functor (R st) where
     fmap _  (R r)       =  R r

Also note that the ExtApplicative case above could not be defined with P_f
rather than R.  P_f has to deal with its argument, and isn't able to when
you would try to apply it like R above. When used applicatively however...

instance  Functor (P_f st) where
    fmap f (P_f p)     =  P_f (\k inp ->  Apply (\(a,r) -> (f a, r)) (p k
inp))

This could be made into a more palatable functor by Yoneda encoding some of
the Step GADT constructors, to carry around any mappings, but that is
irrelevant to this exposition.

The P_m monad uses a mechanism for binding history parsers to future
parsers, which basically lets the context-free future be glued onto a
context-sensitive history.

instance Applicative (P_m st) => Monad (P_m st) where
     P_m  (P_h p, _)  >>=  a2q =
           P_m  (  P_h   (\k -> p (\ a -> unP_m_h (a2q a) k))
                ,  P_f   (\k -> p (\ a -> unP_m_f (a2q a) k))
                )
But the same thing can be done with some modifications to P_m to add a
possible recognizer (R) as an end-state. These represent a monadic
computation with the final batch of applicative or right seminearring
operations that end it separated out.

newtype P_m' state a = P_m (P_h  state a, P_f state a, R state a)
instance Applicative (P_m st) => Monad (P_m st) where
     P_m'  (P_h p, _)  >>=  a2q =
           P_m'  (  P_h   (\k -> p (\ a -> unP_m'_h (a2q a) k))
                ,  P_f   (\k -> p (\ a -> unP_m'_f (a2q a) k))
                ,  P_r   (\k -> p (\ a -> unP_m'_r (a2q a) k))
                )
And then you can drop in special cases for (*>) and (<*) which
mirror the existing code for the ExtApplicative operators of the same name
in uu-parsinglib.

instance  Applicative (P_m st) where
  P_m (hp, fp,rp)  <* P_m (_,_,r)  = P_m  (hp <<* r, fp <<* r, rp <* r)


Now, the a parser written with a substantially unmodified uu-parsinglib can
efficiently evaluate the side of the computation that is being ignored
because any epsilon productions in that side come for free, so all the
fiddly little fmapping that goes on in the Applicative is ignored.

Doaitse could probably do this better justice than I, as I only have a
passing familiarity with the internals of uu-parsinglib.

parsimony can derive a similar benefit by accumulating a right seminnearring
parser as a grammar-algebra off of the base functor for my grammars and
applying that grammar when possible for <*'d fragments in a similar fashion,
but as it only deals with context-free attribute grammars, it has a simpler
job to do.

-Edward Kmett


>  _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20090819/1eb5f011/attachment-0001.html