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

[Edward Kmett]

Please pretend I sprinkled primes liberally through the last two code
fragments. ;)

On Wed, Aug 19, 2009 at 5:00 PM, Edward Kmett <ekmett at gmail.com> wrote:

>  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/f02cb40b/attachment.html