On Tue, Jun 30, 2009 at 7:37 AM, Henning Thielemann < lemming@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