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

[Edward Kmett]

On Tue, Jun 30, 2009 at 7:37 AM, Henning Thielemann <
lemming at henning-thielemann.de> wrote:

>
> On Mon, 29 Jun 2009, Ross Paterson wrote:
>
> The proposal is that the following functions
>>
>>   (<$) :: Functor f => a -> f b -> f a
>>   (*>) :: Applicative f => f a -> f b -> f b
>>   (<*) :: Applicative f => f a -> f b -> f a
>>   some :: Alternative f => f a -> f [a]
>>   many :: Alternative f => f a -> f [a]
>>
> This sounds like a rather ad-hoc extension of the already complicated
> hierarchy of those category classes. Are there particular examples where the
> specialisation is needed and where it cannot be done by optimizer rules? In
> case the specialised functions differ semantically from the default
> implementations - are there generic algorithms that rely on these semantic
> exceptions? Otherwise specialised functons can well be implemented as plain
> functions and don't need to be type class methods.


Yes, there are. Usually the arise when deriving new parser combinators.
uu-parsinglib currently deals with its own 'ExtApplicative' type to get
functionality that could otherwise be readily provided by these methods. In
general, its faster not to bother with the 'pure' parts of an applicative
computation when you know you are going to throw away the result. In
uu-parsinglib this is done with a separate 'R' type of recognizing parser,
but the recognizing parser could be folded into their P_m parser type and
the above instance methods used.

I've been burned by this myself as well. I also have a set of parser
combinators that I've been working on that could currently greatly benefit
from these asymptotically in some places and in the case of a bottom up
monoidal parser I've been working with, the availability of these makes the
difference between termination and non-termination in some cases. In
particular, if you buid up a GADT out of your applicative, you can usually
fold together nodes that differ only in terms of the components generated by
calls to 'pure' when you are down a branch in one of these specialized
cases. When building a parser bottom up, this can dramatically increase
sharing.

It might be nice to also have (<**>) in the patch.

-Edward Kmett
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20090630/77e51ede/attachment.html